期望是有线性性质的
考虑每个点的概率
由于一个点的子树放了后 它就不能再放了
换句话说 这个点是子树中第一个通电的
也就是说这个点的通电概率是\(\frac{1}{size[i]}\)
题目中又说了每个点的编号大于儿子们 于是就不用dfs了 只需递推即可 把所有点的概率相加
那还要求出逆元 这里提供一种逆元的线性递推方式
#include<bits/stdc++.h> #define mod 998244353 #define N 10000005 #define ll long long using namespace std; ll n,fa[N],inv[N],size[N],ans; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=2;i<=n;i++) cin>>fa[i]; inv[1]=1; for(ll i=2;i<=n;i++) inv[i]=mod-mod/i*inv[mod%i]%mod; //递推逆元 for(int i=n;i>=1;i--) size[fa[i]]+=(++size[i]), ans+=inv[size[i]]; cout<<ans%mod; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9804849.html
