题解：P5043 【模板】树同构（[BJOI2015]树的同构）

lyx128 · 2025-08-18 20:25:23 · 题解

本题目考虑使用 map 实现，对于一个无根树，我们考虑找到它的重心（可能有两个），用重心作为新的根，将每棵子树的子节点值保存到 vector 并存到 map 当中，这样不会有哈希的冲突问题，最后比较新根值是否有相同，即有没有树同构。

代码也很简单，示例如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=50;
const int oo=2e9;
int T;
int n;
int u;
struct Edge{
    int v;
    int next;
}e[(N<<1)+5];
int head[N+5],cnt;
int id[N+5],itot;

void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    return ;
}
int dp[N+5];
int sz[N+5];

void dfs(int x,int father){
    sz[x]=1;
    id[x]=++itot;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].v;
        if(v==father)
            continue;
        dfs(v,x);
        sz[x]+=sz[v];
        dp[x]=max(dp[x],sz[v]);
    }
    dp[x]=max(dp[x],n-sz[x]);
    return ;
}
int tot;
map<vector<int>,int> mp;
int lst[N+5];

int push(int x,int father){
    vector<int> a;
    for(int i=head[x];i;i=e[i].next)
        if(e[i].v!=father)
            a.push_back(push(e[i].v,x));
    sort(a.begin(),a.end());
    if(!mp[a])
        mp[a]=++tot;
    return mp[a];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        memset(head,0,sizeof(int)*(n+2));
        cnt=0;
        for(int i=1;i<=n;i++){
            cin>>u;
            if(u)
                add(i,u),add(u,i);
        }
        itot=0;
        memset(dp,0,sizeof(int)*(n+2));
        memset(sz,0,sizeof(int)*(n+2)); 
        dfs(1,0);
        int minn=oo;
        for(int i=1;i<=n;i++)
            minn=min(dp[i],minn);
        int res=oo;
        for(int i=1;i<=n;i++)
            if(dp[i]==minn){
                int id=push(i,0);
                if(lst[id])
                    res=min(lst[id],res);
                else
                    lst[id]=t;
            }
        cout<<((res==oo)?t:res)<<"\n";
    }
    return 0;
}