无根树同构
相当于把树的重心拿出来，看是否相等
cpp
map<vector<int>,int> mp;
int idx=0;
int get(vector<int> &v){
if(!mp.count(v))mp[v]=++idx;
return mp[v];
}
PII cal(){
int n;
cin>>n;
vector<int> adj[n+1];
for(int i=1;i<=n;i++){
int fa;
cin>>fa;
if(fa){
adj[fa].push_back(i);
adj[i].push_back(fa);
}
}
vector<int> h(n+1);
int rt=0,rrt=0,mxsiz=1e9;
function<int(int,int)> get_size=[&](int u,int fa){
int sz=1;
for(auto v:adj[u]){
if(v==fa)continue;
sz+=get_size(v,u);
}
return sz;
};
function<int(int,int,int)> get_wc=[&](int u,int fa,int tot){
int sum=1,ms=0;
for(auto v:adj[u]){
if(v==fa)continue;
int t=get_wc(v,u,tot);
sum+=t;
ms=max(ms,t);
}
ms=max(ms,tot-sum);
if(ms<mxsiz)mxsiz=ms,rt=u,rrt=0;
else if(ms==mxsiz)rrt=u;
return sum;
};
function<void(int,int)> dfs=[&](int u,int fa){
vector<int> tmp;
map<int,int> cnt;
for(auto v:adj[u]){
if(v==fa)continue;
dfs(v,u);
tmp.push_back(h[v]);
}
sort(tmp.begin(),tmp.end());
h[u]=get(tmp);
for(auto v:adj[u]){
if(v==fa)continue;
cnt[h[v]]++;
}
int cur=0,p;
for(auto [x,y]:cnt){
if(y&1)cur++,p=x;
}
};
get_wc(1,0,get_size(1,0));
dfs(rt,0);
int x=h[rt],y=0;
h.assign(n+1,0);
if(rrt){
dfs(rrt,0);
y=h[rrt];
}
if(x>y)swap(x,y);
return {x,y};
}
void solve(){
int m;
cin>>m;
vector<PII> ans(m+1);
for(int i=1;i<=m;i++){
ans[i]=cal();
for(int j=1;j<=m;j++){
if(ans[j]==ans[i]){
cout<<j<<"\n";
break;
}
}
}
}