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

· · 题解

P5043 树同构

这题我用了相对准确的最小表示法来完成（与某个取模 Hash 对拍时，那个 Hash 炸得很惨，不知道是否是写法原因）。

另一篇题解也是最小表示，但是我的实现方式不同。

一、有根树的最小表示

树的括号序列转化：从树根开始执行一次 DFS，每一个结点的子树都有进入和回溯两个过程。DFS 过程中维护一个序列，进入一个子树时向序列中加入一个左括号，回溯时向序列中加入一个右括号，如此可以构成长度为 2\times n 的括号序列。

然而 DFS 过程中，一个点 u 有多个子结点 v_1,v_2,\cdots,v_k，因此在不规定访问顺序的情况下，同一棵树有多种不同的括号序列，其中字典序最小的一个称为这颗有根树的最小表示。

最小表示法的性质：

两颗有根树树同构的充要条件是其最小表示相同。

证明：

充分性：通过最小表示可以唯一确定一棵树的结构：从根节点出发，遇到左括号就向下走一步，遇到右括号就向上走一步，这样的走法在结点无标号时是确定的。树的结构显然唯一确定，因此最小表示相同，树的结构就相同。

必要性：结构相同，DFS 过程完全相同，最小表示显然相同。

最小表示的求法：

DFS 一次即可，设 f_i 表示以 i 为根的子树的最小表示。设一个点 u 的子结点分别为 v_1,\cdots,v_k，则将 f_{v_1},\cdots,f_{v_k} 按字典序从小到大排序，有：

f_u=(f_{v_1}\cdots f_{v_n})

字符之间直接连接。

最坏时间复杂度为 O(n^2)，此为链的情况。

二、无根树的同构

一种简单粗暴的方法：对于树 T，枚举每个点 i 为根求出最小表示 ans_i，令 ans(T)=\min(ans_i)，得到所有最小表示中的字典树最小值。这样，两棵树 T1,T2 同构的充要条件就是 ans(T_1)=ans(T_2)。

这个方法的原理其实是无根树转成有根树，令 ans_i 取到最小值的 i 设为 minroot(T)，则 ans(T_1)=ans(T_2) 即 ans_{minroot(T_1)}=ans_{minroot(T_2)}，而无根树要同构，只需要以某个点为根转化为有根树后同构即可。

该算法完成 这题 的时间复杂度是 O(n^3m)，还有进一步优化的空间。

对于两棵同构树 T，我们只需要快速找到其中两个“同位点”（即在同构树中结构位置相同的点），以这两个同位点为根检验最小表示即可，事实上，任意两个同位点得出的最小表示都应该是相同的。

通常我们选择的同位点是重心。

对于树 T，设其重心为 G_1,G_2（也可能只有 1 个），设 ans(T)=\min(ans_{G_1},ans_{G_2})，则两棵无根树同构当且仅当 ans 值相同。

因此对于每棵树，我们只需要最多检验两个点的最小表示，时间复杂度变成 O(n^2m)。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=60;
int t,n,x,eg,mnp,flg,hd[MAXN],ver[2*MAXN],nx[2*MAXN],sz[MAXN],mx[MAXN];
string mn[MAXN],f[MAXN],g[MAXN],tmp;
void add_edge (int x,int y) {
    ver[++eg]=y;
    nx[eg]=hd[x];
    hd[x]=eg;
    return;
}
void dfs1 (int x,int fa) {
    sz[x]=1;
    for (int i=hd[x];i;i=nx[i]) {
        if (ver[i]==fa) {continue;}
        dfs1(ver[i],x);
        sz[x]+=sz[ver[i]];
        mx[x]=max(mx[x],sz[ver[i]]);
    }
    mx[x]=max(mx[x],n-sz[x]);
    mnp=min(mnp,mx[x]);
    return;
}
void dfs2 (int x,int fa) {
    f[x]="0";
    for (int i=hd[x];i;i=nx[i]) {
        if (ver[i]==fa) {continue;}
        dfs2(ver[i],x);
    }
    int tot=0;
    for (int i=hd[x];i;i=nx[i]) {
        if (ver[i]==fa) {continue;}
        g[++tot]=f[ver[i]];
    }
    sort(g+1,g+tot+1);
    for (int i=1;i<=tot;i++) {f[x]+=g[i];}
    f[x]+="1";
    return;
}
int main () {
    scanf("%d",&t);
    for (int ii=1;ii<=t;ii++) {
        scanf("%d",&n);
        memset(hd,0,sizeof(hd));
        memset(mx,0,sizeof(mx));
        eg=flg=0,mnp=n+1;
        tmp="1";
        for (int i=1;i<=n;i++) {
            scanf("%d",&x);
            if (x) {add_edge(x,i),add_edge(i,x);}
        }
        dfs1(1,0);
        for (int i=1;i<=n;i++) {
            if (mx[i]==mnp) {
                dfs2(i,0);
                tmp=min(tmp,f[i]);
            }
        }
        mn[ii]=tmp;
        for (int i=1;i<=ii-1;i++) {
            if (mn[i]==mn[ii]) {
                printf("%d\n",i),flg=1;
                break;
            }
        }
        if (!flg) {printf("%d\n",ii);}
    }
    return 0;
}