ll calc(ll x) {
	return pre[x];
}
void dfs(int x,int fa) {
	sz[x]=1;
	f[x][sz[x]][0]=1;
	for(int to:g[x]) {
		if(to==fa) continue;
		dfs(to,x);
		sz[x]+=sz[to];
		for(int i=sz[x];i>=1;i--) {
		    ll a0=f[x][i][0],a1=f[x][i][1];
		    f[x][i][0]=f[x][i][1]=0;
			for(int j=sz[to];j>=1;j--) {
                (f[x][i][0]+=(a1*f[to][j][0]%p))%=p;
				(f[x][i][0]+=(a0*f[to][j][1]%p))%=p;
				(f[x][i][1]+=(a0*f[to][j][0]%p))%=p;
				(f[x][i][1]+=(a1*f[to][j][1]%p))%=p;	
				if(j<=i-scc[x]) {
					(f[x][i][0]+=(f[x][i-j][1]*f[to][j][1]%p*calc((i-j)*j-1)%p))%=p;
					(f[x][i][0]+=(f[x][i-j][0]*f[to][j][0]%p*calc((i-j)*j-1)%p))%=p;
					(f[x][i][1]+=(f[x][i-j][1]*f[to][j][0]%p*calc((i-j)*j-1)%p))%=p;
					(f[x][i][1]+=(f[x][i-j][0]*f[to][j][1]%p*calc((i-j)*j-1)%p))%=p;
				}	
			}
		}
	}
}

题目数据范围是 $n=5000$，但实测 $n=1000$ 要跑 $30s$。

有没有大佬能帮忙看下是复杂度错误还是常数太大，十分感谢。