Nowcoder156F 托米的游戏 期望

传送门

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

---

 

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

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

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100010 , MOD = 998244353;
struct Edge{
    int end , upEd;
}Ed[MAXN << 1];
int head[MAXN] , dep[MAXN] , N , sum , cntEd;

inline void addEd(int a , int b){
    Ed[++cntEd].end = b;
    Ed[cntEd].upEd = head[a];
    head[a] = cntEd;
}

inline long long poww(long long a , int b){
    long long times = 1;
    while(b){
        if(b & 1)
            times = times * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return times;
}

void dfs(int now , int fa){
    dep[now] = dep[fa] + 1;
    sum = (sum + poww(dep[now] , MOD - 2)) % MOD;
    for(int i = head[now] ; i ; i = Ed[i].upEd)
        if(!dep[Ed[i].end])
            dfs(Ed[i].end , now);
}

int main(){
    cin >> N;
    for(int i = 1 ; i < N ; i++){
        int a , b;
        cin >> a >> b;
        addEd(a , b);
        addEd(b , a);
    }
    dfs(1 , 0);
    cout << sum % MOD;
    return 0;
}