牛客网练习赛23F托米的游戏题解
题意：
给定n个点的一棵树，根为1。每次操作随机选点，把选中的点的子树删去。当所有点被删去则停止。求操作次数的期望。
思路：
按照套路，根据期望的线性性，和的期望等于期望的和，
考虑一个点被删除时只有两种情况(默认根的深度为1)：
(1).选中自己被删除，此时贡献为1，概率为
。
(2).选中该点的祖先，此时贡献为0，贡献应该被算在祖先处，概率为
。
PS：删除其他点并不会导致该点被删除，不会对它的概率产生影响。 因此单点的期望贡献为%3D%5Cfrac%7B1%7D%7Bdep_i%7D*1%2B%5Cfrac%7Bdep_i-1%7D%7Bdep_i%7D*0%3D%5Cfrac%7B1%7D%7Bdep_i%7D)
所以%3D%5CSigma_%7Bi%3D1%7D%5En%5Cfrac%7B1%7D%7Bdep_i%7D)
复杂度O(nlog mod),dfs求出所有点的深度，再求一下乘法逆元)
内容板块
数学 ：期望 乘法逆元
#include<cstdio>
#define rep(i,s,t) for(register int i=s;i<=t;++i)
#include<vector>
using namespace std;
const int N=100005,mod=998244353;
vector<int>to[N];
inline int fp(int a,int b){ int res=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1)
res=1ll*res*a%mod; return res;
}
int dep[N],n;
inline void dfs(int u,int fa,int deep){
dep[u]=deep;
for(auto v:to[u]){
if(v==fa)continue;
dfs(v,u,deep+1); }
}
#define pb push_back
int main(){
scanf("%d",&n);
rep(i,2,n){ int x,y;
scanf("%d%d",&x,&y);
to[x].pb(y),to[y].pb(x);
}
dep[1]=1;
dfs(1,1,1);
int ans=0;
rep(i,1,n)
ans=(ans+fp(dep[i],mod-2))%mod;
printf("%d\n", ans);
return 0;
} 
