众所周知 oiwiki 的三个树哈希都似了。所以我们需要点别的东西。
邓老师的博客里有这样一种树哈希：子树 \(x\) 的哈希值 \(h(x)\) 为 \(1+\sum_{v\in son_x}f(h(v))\)，\(f\) 是你随便写的一个随机函数。
优点是非常好写，而且目前好像卡不掉。
对于洛谷板子是无根树，找到重心就行了。如果有两个那就两个都跑一遍。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <random>
#include <chrono>
#define ull unsigned long long
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ull st=rnd();
int n,m;
struct node{
int v,next;
}edge[110];
int t,head[110];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
pair<ull,ull>ans[110];
ull hs[110];
ull getrand(ull x){
x^=x<<13;x^=x>>7;x^=x<<17;
return x;
}
int rt,rt2,sum,size[110];
void findrt(int x,int f){
size[x]=1;int mx=0;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
findrt(edge[i].v,x);
size[x]+=size[edge[i].v];
mx=max(mx,size[edge[i].v]);
}
}
mx=max(mx,n-size[x]);
if(mx<sum)sum=mx,rt=x,rt2=0;
else if(mx==sum)rt2=x;
}
void dfs(int x,int f){
hs[x]=st;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs(edge[i].v,x);
hs[x]+=getrand(hs[edge[i].v]);
}
}
}
void solve(int x){
sum=0x3f3f3f3f;t=rt=rt2=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int f;scanf("%d",&f);
if(f)add(f,i),add(i,f);
}
findrt(1,0);
dfs(rt,0);ans[x].first=hs[rt];
if(rt2)dfs(rt2,0),ans[x].second=hs[rt2];
if(ans[x].first<ans[x].second)swap(ans[x].first,ans[x].second);
for(int i=1;i<=n;i++)head[i]=0;
}
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++)solve(i);
for(int i=1;i<=m;i++){
for(int j=1;j<=i;j++){
if(ans[i]==ans[j]){
printf("%d\n",j);break;
}
}
}
return 0;
}