题意：给出一棵树，在每一轮中，随机选择一个点将它与它的子树割掉，最后割掉所有点时游戏结束，问游戏期望进行多少轮。$N \leq 10^5$

---

 

和的期望等于期望的和，我们考虑每一个点对最后答案的贡献。

考虑到如果把某一个点$u$的任意一个祖先割掉，$u$就不会产生贡献，而只有在割掉$u$的祖先之前割掉$u$，$u$才能产生$1$的贡献，所以对于某一个点$u$，它产生贡献的概率为$\frac{1}{dep_u}$，所以我们求一边$\sum\frac{1}{dep_i}$就可以了

1 #include
     
       2 using namespace std; 3  4 const int MAXN = 100010 , MOD = 998244353; 5 struct Edge{ 6     int end , upEd; 7 }Ed[MAXN << 1]; 8 int head[MAXN] , dep[MAXN] , N , sum , cntEd; 9 10 inline void addEd(int a , int b){11     Ed[++cntEd].end = b;12     Ed[cntEd].upEd = head[a];13     head[a] = cntEd;14 }15 16 inline long long poww(long long a , int b){17     long long times = 1;18     while(b){19         if(b & 1)20             times = times * a % MOD;21         a = a * a % MOD;22         b >>= 1;23     }24     return times;25 }26 27 void dfs(int now , int fa){28     dep[now] = dep[fa] + 1;29     sum = (sum + poww(dep[now] , MOD - 2)) % MOD;30     for(int i = head[now] ; i ; i = Ed[i].upEd)31         if(!dep[Ed[i].end])32             dfs(Ed[i].end , now);33 }34 35 int main(){36     cin >> N;37     for(int i = 1 ; i < N ; i++){38         int a , b;39         cin >> a >> b;40         addEd(a , b);41         addEd(b , a);42     }43     dfs(1 , 0);44     cout << sum % MOD;45     return 0;46 }