题意

较好理解，计算一棵树上随机断边成为链的期望操作次数。

思路

Thanks to 某大佬。

我们考虑断边顺序的排列，那么答案就是所有排列中使条件成立的最短前缀长度的和除以 (n−1)!。

尝试研究一下这个和，发现对于某个前缀长度，我们只需计算出该长度合法的方案数，减去小于该长度合法的方案数即可算出这个长度作为最短前缀长度的方案数。然后方案数乘上长度求和就可以得到上面的和。

可以发现该做法和官方做法本质相同，但这里提供另一种思维路线。

我们 dp，设 fi,j,k 表示 i 的子树中，删去 j 条边，有 k 条边连在 i 节点上的合法情况数。

然后我们用类似树形背包的方式转移，初始化情况只有 i 节点，依次枚举儿子节点，再枚举该儿子节点多删去边的数量，分别乘法原理更新该儿子节点是否连到 i 节点情况数。

根据结论可知，该做法复杂度为 O(n2)。

代码

参考官方题解代码

需要注意本题稍微有点卡空间。

#include<bits/stdc++.h>
using namespace std;
const long long mod=985661441;
unsigned int dp[5005][5005][3],siz[5005],f[5005][3];
int fra[5005]={1},inv[5005];
int n;
vector<int> so[5005];
int ksm(int x,int y){
    int t=1;
    while(y){
        if(y&1) t=1ll*t*x%mod;
        x=1ll*x*x%mod;y>>=1;
    }
    return t;
}
void dfs(int x){
    siz[x]=1;dp[x][0][0]=1;
    for(auto v:so[x]){
        dfs(v);
        for(int i=0;i<=siz[x]+siz[v];i++) f[i][0]=f[i][1]=f[i][2]=0;
        for(int i=0;i<siz[x];i++){//树形背包
            for(int j=0;j<siz[v];j++){
                long long g=(dp[v][j][0]+dp[v][j][1]+dp[v][j][2])%mod;
                //与该儿子断开
                f[i+j+1][0]=(f[i+j+1][0]+dp[x][i][0]*g%mod)%mod;
                f[i+j+1][1]=(f[i+j+1][1]+dp[x][i][1]*g%mod)%mod;
                f[i+j+1][2]=(f[i+j+1][2]+dp[x][i][2]*g%mod)%mod;
                //与该儿子连接
                f[i+j][1]=(f[i+j][1]+1ll*dp[x][i][0]*(dp[v][j][0]+dp[v][j][1])%mod)%mod;
                f[i+j][2]=(f[i+j][2]+1ll*dp[x][i][1]*(dp[v][j][0]+dp[v][j][1])%mod)%mod;
            }
        }
        siz[x]+=siz[v];
        for(int i=0;i<siz[x]+siz[v];i++){
            dp[x][i][0]=f[i][0];
            dp[x][i][1]=f[i][1];
            dp[x][i][2]=f[i][2];
        }
    }
}
signed main(){
    for(int i=1;i<=5000;i++) fra[i]=1ll*fra[i-1]*i%mod;
    inv[5000]=ksm(fra[5000],mod-2);for(int i=5000-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
    cin>>n;
    for(int i=2;i<=n;i++){
        int tmp;cin>>tmp;
        so[tmp].push_back(i);
    }
    dfs(1);
    long long sum=0,ans=0;
    for(int i=0;i<n;i++){
        long long F=1ll*(dp[1][i][0]+dp[1][i][1]+dp[1][i][2])%mod*inv[n-1]%mod*fra[n-1-i]%mod*fra[i]%mod;
        F=F-sum;if(F<0) F+=mod;//计算最短合法前缀方案数
        sum+=F;sum%=mod;
        ans=(ans+(F*i)%mod)%mod;//统计期望
    }
    cout<<ans;
    return 0;
}