树同构判断的多种方法

· · 题解

Part1 前言

我在一年前写过树同构，但那种方法是复杂度极高且容易产生冲突的，一年之后，我想要介绍三种方法，其中一种较慢但是确定性算法，另外两种保证线性但是基于数值哈希的方式，但并没有通用 Hack，即 Hack 方式仅限于对着代码卡。

Part2 确定性算法

考虑对一棵有根树进行哈希，定义一棵有根树的哈希值为其所有子树哈希值组成的数组排序后的结果，这是一个 vector，我们每加入一个 vector 就用 map 给它标号。

这样可以做到绝对正确，但我们只做到了有根树，时间复杂度为 O(n^2\log n)。

考虑一棵无根树最多有两个重心，我们可以对每一个重心分别哈希，然后取最值。

于是得到了本题的做法，时间 O(NS\log S)，空间 O(\sum n^2)，其中 N=\max n,S=\sum n。

代码片段：

int calc(int x,int pr){
    vector<int>a={-1};
    for(int y:lk[x])
        if(y!=pr)a.push_back(calc(y,x));
    sort(a.begin(),a.end());
    if(!mp[a])mp[a]=++mt;
    return mp[a];
}

Part3 较劣的非确定性算法

上面发现，我们每获得一个 vector 就将其插入了 map 内，而 vector 的比较是 O(n) 的，所以我们可以对于每一个 vector 进行字符串哈希后再插入 map，这样就变成了时间 O(S\log S)，空间 O(S)。

代码片段：

int calc(int x,int pr){
    vector<int>a={0};
    for(int y:lk[x])
        if(y!=pr)a.push_back(calc(y,x));
    sort(a.begin(),a.end());
    ul res=0;
    for(int p:a)res=res*C+rp[p];
    if(!mp[res])mp[res]=++mt;
    return mp[res];
}

Part4 较优的非确定性算法

其实我认为这个算法比上面更优是因为其更简便且更好用。

它是基于和哈希的，但我们不能单纯地将儿子的哈希值加起来，这样会有通用卡法，甚至你随便拍几组就挂了。

所以需要对儿子节点的哈希值做多项式变换，即让一个函数作用于它。

然后你会发现可以用换根 dp 在 O(n) 的时间内求出以所有节点为根的哈希值，然后就可以暴力取最值了。

于是本题优化到了时空 O(S) 十分优秀。

代码片段：

void dfs(int x,int pr){
    h1[x]=13;if(pr){
        auto it=lk[x].begin();
        while(*it!=pr)++it;lk[x].erase(it);
    }
    for(int y:lk[x])
        dfs(y,x),h1[x]+=F(h1[y]);
}
void dp(int x,int pr){
    if(pr)h2[x]=h1[x]+F(h2[pr]-F(h1[x]));
    else h2[x]=h1[x];
    for(int y:lk[x])dp(y,x);
    lk[x].clear();
}

以上三种算法均可以通过本题和 SPOJ 加强版。

Part5 后记

马上就要省选了，HNOI2023rp++！

过了样例 \Leftrightarrow 得分在 [0,100] 之间。