正題

題目鏈接:https://www.luogu.com.cn/problem/CF280C

---

題目大意

$n$個點的一棵樹，每次選擇一個沒有染色的點把它和它的子樹染黑，求期望全部染黑的步數。

---

解題思路

可以理解為我們按照一個順序輪流染色，如果一個點有祖先節點在它前面就不用計算貢獻。

也就是如果一個點要計算貢獻的概率就是它要排在所有它的祖先節點前面，也就是$\frac{1}{de{p}_x}$。求個和就好了。

時間復雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e5+10; int n;double ans; vector<int> G[N]; void dfs(int x,int fa,int dep){for(int i=0;i<G[x].size();i++){int y=G[x][i];if(y==fa)continue;dfs(y,x,dep+1);}ans+=1.0/(double)dep;return; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}dfs(1,0,1);printf("%.10lf\n",ans); }

總結

以上是生活随笔為你收集整理的CF280C-Game on Tree【数学期望】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。