题意

给定 $m$ 棵树，求每个树最早出现的同构树（改变编号后形态一样的多颗树）。

思路

首先，我们要确定每颗树的形态。

因为每颗树的结点数极小，因此可以枚举每个结点作为根结点（或者用树的重心）。

对于确定树的形态，跑一遍树哈希。

因为我们最后的匹配只是核对哈希值是否相等，因此每颗树存一个最值就好了。

上代码：

#include<bits/stdc++.h>
const long long base=98243;
using namespace std;
struct ed {
    int u,v,nxt;
}edge[5000];
int N[5000],M,number;
int head[5000];
unsigned long long ans[5000];
unsigned long long siz[500];
void add(int u,int v) {
    number++;
    edge[number].nxt=head[u];
    edge[number].u=u;
    edge[number].v=v;
    head[u]=number;
}
unsigned long long check(int root,int fa) {
    int top=0;
    unsigned long long x[500],answer=0;
    siz[root]=1;
    for(int i=head[root];i;i=edge[i].nxt) {
        int v=edge[i].v;
        if(v==fa)
            continue;
        top++;
        x[top]=check(v,root);
        siz[root]+=siz[v];
    }
    sort(x+1,x+top+1);
    for(int i=1;i<=top;i++)
        answer=answer*base+x[i];
    return answer*siz[root]+1;
}
int main() {
    int u;
    scanf("%d",&M);
    for(int i=1;i<=M;i++) {
        number=0;
        memset(head,0,sizeof(head));
        scanf("%d",&N[i]);
        for(int j=1;j<=N[i];j++) {
            scanf("%d",&u);
            if(u!=0) {
                add(u,j);
                add(j,u);
            }
        }
        for(int j=1;j<=N[i];j++)
            ans[i]=max(check(j,0),ans[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;
}

完结撒花~