O(n)T3求hack

#include<bits/stdc++.h>
#define ll long long
#define str string
#define rd read()
#define rt write
using namespace std;
inline int read(){
	char c;
	int x=0,f=1;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x*=10;
		x+=c-'0';
		c=getchar();
	}
	return f*x;
}
const int N=8e3+10;
int top[N],sz[N],son[N],fa[N],dpt[N];
vector<int>vc[N];
long long w[N],gx[N];
void dfs1(int u,int f){
	dpt[u]=dpt[f]+1;
	fa[u]=f;
	sz[u]=1;
	for(auto it:vc[u]){
		if(it==f) continue;
		dfs1(it,u);
		sz[u]+=sz[it];
		if(sz[it]>sz[son[u]]) son[u]=it;
	}
} 
void dfs2(int u,int f){
	if(son[f]==u) top[u]=top[f];
	else top[u]=u;
	if(son[u]) dfs2(son[u],u);
	for(auto it:vc[u]){
		if(it==f||it==son[u]) continue;
		dfs2(it,u);
	}
}
void sol(int u,int f){
	if(son[u]){
		sol(son[u],u);
		gx[u]=gx[son[u]];
		w[u]=w[son[u]]+1;
	}else{
		w[u]=0,gx[u]=1;
	}
	for(auto it:vc[u]){
		if(it==f||it==son[u]) continue;
		sol(it,u);
		gx[u]+=gx[it];
		w[u]=max(w[u],w[it]+1);
	}
	if(son[u]) gx[u]+=w[u]+1;
	if(u==son[f]) return;
	if(gx[u]<=1ll*sz[u]*dpt[f]){
		w[f]+=sz[u];
		gx[u]=0;
	}
}
int main(){
	int t=rd;
	while(t--){
		int n=rd,m=rd;
		for(int i=1;i<=n;i++) vc[i].clear();
		memset(son,0,sizeof(son));
		memset(sz,0,sizeof(sz));
		memset(w,0,sizeof(w));
		memset(gx,0,sizeof(gx));
		dpt[1]=0;
		for(int i=2;i<=n;i++){
			int fu=rd;
			vc[i].emplace_back(fu);
			vc[fu].emplace_back(i);
		}
		dfs1(1,1),dfs2(1,1);
		sol(1,1);
		cout<<gx[1]<<'\n';
	}
	return 0;
}