链接：https://www.nowcoder.com/acm/contest/156/F 来源：牛客网 题目描述 题目背景编不下去了 托米有一棵有根树 T, 树根为1，每轮他会在剩下的子树中等概率一个点 u, 砍掉 u 的子树 (包含 u)，如果树上的点都被砍光了，游戏结束。 求出这个游戏进行的期望轮数，可以证明这个数一定是有理数，设他为 , 你需要告诉他一个整数 x 满足 输入描述: 第一行输入一个数 n， 表示 T 的点数，下面 n-1 行给出了 T 的每条边 输出描述: 一行一个整数表示答案 示例1 输入 复制 3 1 2 1 3 输出 复制 2 备注: n ≤ 105
当前节点只和他上面的点有关，删他下面的和旁边的无关，所以概率就是1/深度；
mod是素数；费马
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> using namespace std; #define ll long long vector<int>p[100010]; int deep[100010]; #define mod 998244353 void dfs(int x,int pre) { for(int i=0;i<p[x].size();i++) { if(p[x][i]==pre) continue; deep[p[x][i]]=deep[x]+1; dfs(p[x][i],x); } } ll qsm(ll a,ll b,ll c) { ll ans=1; while(b) { if(b&1) ans=ans*a%c; b=b/2; a=a*a%c; } return ans; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int x,y; scanf("%d%d",&x,&y); p[x].push_back(y); p[y].push_back(x); } deep[1]=1; dfs(1,1); // cout<<deep[1]<<" "<<deep[2]<<" "<<deep[3]<<endl; long long ans=0; for(int i=1;i<=n;i++) { ans=ans+qsm(deep[i],mod-2,mod); ans=ans%mod; } cout<<ans<<endl; return 0; }