期望是有线性性质的

考虑每个点的概率

由于一个点的子树放了后 它就不能再放了

换句话说 这个点是子树中第一个通电的

也就是说这个点的通电概率是\(\frac{1}{size[i]}\)

题目中又说了每个点的编号大于儿子们 于是就不用dfs了 只需递推即可 把所有点的概率相加

那还要求出逆元 这里提供一种逆元的线性递推方式

#include
    
     #define mod 998244353 #define N 10000005#define ll long longusing 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<