一个树，0号节点是它的根，1到n-1号节点依次，等概率地认已经确定地节点为爸爸。比如k就等概率地认0-k-1中的一个为爸爸。每个点都有一个权值，随机选一个点，求它子树大小，对所有的树，所有的点，求期望。
首先，枚举树所有的情况，再枚举树上所有的点，显然是不现实的。 我们把每个点单独考虑，每个编号的点在每种树中，被选中的概率是多少。 n个点的树有（n-1）！种构造方法 0号节点出现概率为 1/n*1/n*n = 1/n 。。。。。。。。 写到4，5个节点的树后会发现，将分母通分为n！， 0号节点频率为（n-1）！/n！ 1号:(n-1)!+(n-1)!/1/n 2号:(n-1)!+(n-1)!/1+(n-1)!/2/n! 以此类推。 需要用到逆元
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 100010; const int mod = 998244353; int t,n; LL Qpow(LL x,LL n) { LL res = 1; while(n) { if(n&1) res = (res*x)%mod; n>>=1; x = (x*x) %mod; } return res; } LL inv(LL a) { return Qpow(a,mod-2); } int main() { cin>>t; while(t--) { scanf("%d",&n); LL tmp = 1; for(int i=1;i<n;i++) { tmp = tmp*i%mod; } //printf("tmp = %lld\n",tmp); LL a; scanf("%lld",&a); LL ans = tmp*a%mod; LL d = tmp; //printf("d = %lld\n",d); for(int i=1;i<n;i++){ scanf("%lld",&a); d = (d+tmp*inv(i)%mod)%mod; //printf("d = %lld\n",d); ans = (ans+d*a%mod)%mod; } ans = ans*inv(tmp*n%mod)%mod; printf("%lld\n",ans); } }