树同构

· · 算法·理论

前置知识：图的遍历，树的重心。

树同构是一种快速判断两棵树是否本质相同的算法。这里本质相同在不同种类的树中有不同定义。

有标号树的判定是好做的。对于有标号有根树，我们从根节点开始 \text{DFS}，钦定每次先走标号小的儿子，最后判定 \text{DFS} 序是否相同即可。对于有标号无根树，钦定 1 为根节点即可，执行相同操作即可。以下重点讲解无标号树。

AHU 树同构

有根树

我们考虑无标号有根树怎么做。我们有 \text{AHU} 树同构算法。其核心为一棵树的括号序列。我们如下构造：

  2. 递归 u 的子树。

比如，以下一棵树：

其括号序为：1 \ 2 \ 4 \ 4 \ 5 \ 5 \ 6 \ 6 \ 2 \ 3 \ 7 \ 8 \ 9 \ 9 \ 8 \ 7 \ 3 \ 1。

这是对于有标号树有根树的定义。对于无根树，我们改为在初次进入时加入 0，最终离开时加入 1，以表示遍历该树时的出入栈情况。我们发现，这样每个节点 u 的子树的答案即为将它所有儿子的子树答案拼接起来，在前面加入 0，后面加入 1。 :::warning[注意事项]

  1. 为了不让括号序受输入顺序的影响，在拼接儿子答案时，要从字典序从小到大拼接。 ::: :::info[参考实现] 
    string ahu(int u,int fath)
{
int v,cnt=0,i;
string nw,a[60];
nw="0";
for(i=0;i<s[u].size();i++)
{
    v=s[u][i];
    if(v==fath)
        continue;
    cnt++;
    a[cnt]=ahu(v,u);
}
sort(a+1,a+cnt+1);
for(i=1;i<=cnt;i++)
    nw+=a[i];
nw+="1";
return nw;
}

    ::: 对于无标号有根树，我们比较该函数返回值即可，时间复杂度 \text{O} (T n \log n)，其中 T 为树的数量。

    无根树

    我们考虑无标号无根树怎么做，也就是这道题：【模板】树同构（[BJOI2015]树的同构）。

无根树一般考虑钦定根。寻找树上与标号无关的特征点，常见的是重心。于是我们找出树中的重心，钦定它为根，套用无根树做法即可。

注意一棵树可能有两个重心，我们取二者答案中字典序较大的那个。 :::info[参考实现]

maxsz[0]=n;
getsz(1,0);
rt=getrt(1,0,n);
for(j=1;j<=n;j++)
{
    if(maxsz[j]==maxsz[rt])
        ans[i]=max(ans[i],ahu(j,0));
}

::: 比较两棵树的 ans 数组即可判断二者是否同构。时间复杂度 \text{O} (T n \log n)，其中 T 为树的数量。

树同构应用较少，故不给出题单。