长剖做法20pts求条

#include<bits/stdc++.h>
using namespace std;
const int N=8005;
int n,m,mxd[N],son[N],sz[N],mx[N][805];
vector<int> G[N];
int *dp[N][805],buf[N*800*5],*now=buf;
void dfs(int u){
	sz[u]=1;
	for(auto v:G[u]){
		dfs(v);
		sz[u]+=sz[v];
		if(mxd[v]>mxd[son[u]]) son[u]=v;
	}
	mxd[u]=mxd[son[u]]+1;
}
int getdp(int u,int i,int j){
	if(j<mxd[u]) return dp[u][i][j];
	return i*sz[u];
}
void dfs2(int u){
	if(son[u]){
		for(int i=1;i<=m;i++)
			dp[son[u]][i]=dp[u][i]+1;
		dfs2(son[u]);
		for(int i=1;i<m;i++)
			dp[u][i][0]=dp[son[u]][i+1][0];
	}
	else{
		for(int i=1;i<=m;i++) dp[u][i][0]=i;
		return;
	}
	int cmxd=0;
	for(auto v:G[u]){
		if(v==son[u]) continue;
		cmxd=max(cmxd,mxd[v]);
		for(int i=1;i<=m;i++)
			dp[v][i]=now,now+=mxd[v]+2;
		dfs2(v);
	}
	for(int i=1;i<=m;i++){
		int tmp=getdp(son[u],i,i-1);
		if(i<m) mx[i][0]=dp[son[u]][i+1][0]-tmp;
		for(int j=1;j<=min(i,cmxd);j++)
			mx[i][j]=dp[son[u]][i][j-1]-tmp;
	}
	for(int i=1;i<=m;i++)
		for(int j=0;j<=mxd[u];j++)
			dp[u][i][j]+=i;
	for(auto v:G[u]){
		if(v==son[u]) continue;
		for(int i=1;i<=m;i++){
			int tmp=getdp(v,i,i-1);
			if(i<m){
				dp[u][i][0]+=tmp;
				int dif=dp[v][i+1][0]-tmp;
				if(dif>mx[i][0])
					dp[u][i][0]+=dif-mx[i][0],mx[i][0]=dif;
			}
			for(int j=0;j<mxd[v];j++){
				dp[u][i][j+1]+=tmp;
				int dif=dp[v][i][j]-tmp;
				if(dif>mx[i][j+1])
					dp[u][i][j+1]+=dif-mx[i][j+1],mx[i][j+1]=dif;
			}
		}
	}
}
void solve(){
	cin>>n>>m;m++;
	for(int i=1;i<=n;i++) 
		G[i].clear(),mxd[i]=son[i]=sz[i]=0;
	for(int i=2,x;i<=n;i++)
		cin>>x,G[x].push_back(i);
	dfs(1);
	now=buf;
	for(int i=1;i<=m;i++)
		dp[1][i]=now,now+=mxd[1]+2;
	dfs2(1);
	cout<<dp[1][1][0]<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}