一个局面被删空的操作次数,等于所有路径被删的时刻的最大值,我们做差分,对每个时刻求仍有路径存在的概率,求和即可。
我们求全部删完的概率,不妨对每个 $j$ 求出所有操作共覆盖了恰 $j$ 个点删完了所有路径的方案数(容易转概率),设计 $f(i,j,k)$ 表示考虑到子树 $i$ 子树内选了 $j$ 个点仍存在的路径最深到 $k$ 结束,第二维可以类树上背包分析,第三维再前缀和一下,转移复杂度 $O(n^3)$。所求即为: $$ 1+\sum_{i=1}^{\infty}\sum_j\frac{{n\choose j}j!{i\brace j}}{n^i}(1-f(1,j))=1+\sum_j\frac{n}{n-j}(1-f(1,j)) $$
const int N=305;
int n,m;
int fa[N],dp[N];
vec<int> v[N],g[N];
mint f[N][N][N],t[N][N],fc[N],iv[N];
int sz[N];
il mint C(int n,int m){return fc[n]*iv[m]*iv[n-m];}
void INIT(){
n=300;
fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;
iv[n]=1/fc[n];per(i,n,1)iv[i-1]=iv[i]*i;
}
void MAIN(){
read(n,m);
rep(i,2,n)read(fa[i]),g[fa[i]].pub(i);
rep(i,1,m){int a,b;read(a,b);v[b].pub(a);}
rep(i,1,n)dp[i]=dp[fa[i]]+1;
per(x,n,1){
sz[x]=1;
int td=0;for(auto z:v[x])chmax(td,dp[z]);
rep(k,td,dp[x])f[x][0][k]=1;
for(auto y:g[x]){
MSET(t,0);
rep(i,0,sz[x])rep(j,0,sz[y])
rep(k,0,dp[x])t[i+j][k]+=f[x][i][k]*f[y][j][k]-(k?f[x][i][k-1]*f[y][j][k-1]:0);
sz[x]+=sz[y];
rep(i,0,sz[x])rep(j,0,dp[x])f[x][i][j]=t[i][j];
rep(i,0,sz[x])rep(j,1,dp[x])f[x][i][j]+=f[x][i][j-1];
}
per(i,sz[x]-1,0){mint t=f[x][i][dp[x]];rep(j,0,dp[x])f[x][i+1][j]+=t;}
}
mint ans=1;
repl(j,1,n)ans+=(1-f[1][j][0]/C(n,j))*n/(n-j);
put(ans);
}