暴力DP求调

#include<bits/stdc++.h>
#define N 8005
using namespace std;
int fa[N];
vector<int> g[N];
int dp[505][505][505],tmp[505][505];
int siz[N];
int ans=0;
void dfs(int u){
	dp[u][0][1]=0;
	dp[u][1][0]=0;
	siz[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		dfs(v);
		siz[u]+=siz[v];
	}
	for(int c=0;c<g[u].size();c++){
		int v=g[u][c];
		for(int i=0;i<=siz[u];i++){
			for(int j=0;j<=siz[u];j++)tmp[i][j]=INT_MIN;
		}
		for(int i=siz[u];i>=0;i--){
			for(int j=siz[u];j>=0;j--){
				for(int a=i;a>=0;a--){
					for(int b=j;b>=0;b--){
						tmp[i][j]=max(max(dp[u][a][j-b]+dp[v][i][b],dp[u][i][j]),dp[u][i][j-b]+dp[v][a][b]);
					}
				}
			}
		}
		for(int i=0;i<=siz[u];i++){
			for(int j=0;j<=siz[u];j++)dp[u][i][j]=max(dp[u][i][j],tmp[i][j]);
		}
	}
	for(int i=0;i<=siz[u];i++){
		for(int j=0;j<=siz[u];j++){
			for(int k=1;k<=siz[u];k++){
				if(i+k>siz[u]||j-k<0)continue;
				dp[u][i+k][j-k]=max(dp[u][i+k][j-k],dp[u][i][j]);
			}
		}
	}
	for(int i=0;i<=siz[u];i++){
		for(int j=0;j<=siz[u];j++)dp[u][i][j]+=i;
	}
	for(int i=0;i<=siz[u];i++){
		for(int j=0;j<=siz[u];j++)ans=max(ans,dp[u][i][j]);
	}
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)g[i].clear();
		ans=0;
		for(int i=2;i<=n;i++){
			cin>>fa[i];
			g[fa[i]].push_back(i);
		}
		dfs(1);
		cout<<ans<<"\n";
	}
	return 0;
}