awdec's Blog

用于判断有根树与无根树同构。

有根树同构

对于两棵有根树 $T_{1} (V_{1}, E_{1}, r_{1})$ 和 $T_{2} (V_{2}, E_{2}, r_{2})$ ，如果存在一个双射 $φ : V_{1} \to V_{2}$ ，使得 $\forall u, v \in V_{1}, (u, v) \in E_{1} \Leftrightarrow (φ (u), φ (v)) \in E_{2}$ 且 $φ (r_{1}) = r_{2}$ 则称 $T_{1}, T_{2}$ 同构。

无根树同构

和有根树同构类似，没有 $φ (r_{1}) = r_{2}$ 的限制。

简单地，对于无根树如果能通过对其中一棵树的节点进行重新标号使得和另一棵树完全相同，则称这两棵无根树同构。

无根树同构可以转换成有根树同构，具体而言：

若两棵无根树的重心数量不同，则不同构。
若都只有一个重心，以各自唯一重心为根后判断有根树同构。
若都有两个重心，不能在两棵树中各自任取一个重心作为根，因为同构映射可能交换两个重心。可以分别计算以两个重心为根的规范编码，再比较排序后的两个编码；也可以删去两重心之间的边，在该边中插入一个虚根并连接两个重心，然后统一以虚根为根。

所以用于解决有根树同构的算法也可以解决无根树同构。

AHU：

一段合法的括号序和一棵有序有根树唯一对应，而且一棵树的括号序由各棵子树的括号序按子节点顺序拼接而成。

括号序用 0 表示递归该节点，1 表示从该节点回溯。

本文讨论的普通树没有固定的子节点顺序。为了得到无序有根树的唯一规范编码，需要先递归求出所有子树编码，将它们排序后再拼接；任意调整拼接顺序只会得到同一无序树的不同有序表示，不能直接作为唯一编码。

所以判断两棵无序有根树同构，可以比较排序子树编码后得到的规范括号序。

朴素做法：

朴素地用 vector 存下每一棵子树的括号序，按从小到大升序拼接子树的括号序作为当前节点的括号序。

最坏情况下，若树是“毛毛虫”，那么拼接括号序的过程是 $O (n^{2})$ 的。

点击展开代码

cpp

string q[N];
void dfs1(int x, int y) {
    vector<string> tmp;
    q[x] = "0";
    for (auto u : p[x]) {
        if (u == y)
            continue;
        dfs1(u, x);
        tmp.push_back(q[u]);
    }
    sort(tmp.begin(), tmp.end());
    for (auto u : tmp)
        q[x] += u;
    q[x] += "1";
}

优化：

一个节点的无序子树类型由“所有儿子子树类型编号组成的有序序列”唯一确定。因此可以把排序后的儿子编号序列离散化成一个整数，代替完整括号序。关键不是节点处于同一深度，而是所有待比较的树必须共享同一份“规范序列 $\to$ 类型编号”映射；比较两棵树时，不能在处理第二棵树前清空 mp 或重置编号。

后序遍历保证计算当前节点时，所有儿子的类型编号已经确定。构造所有 tmp 的总元素数为 $O (n)$ ，但单个序列的排序、复制以及 map<vector<int>, int> 的字典序比较都不是 $O (1)$ 。

设 $n$ 为所有待比较树的总节点数，当前节点度数为 $d_{x}$ 。对子编号排序的总代价为 $O (\sum_{x} d_{x} \log d_{x})$ ；map 每次操作需要 $O (\log n)$ 次比较，每次向量比较最坏为 $O (d_{x} + 1)$ 。利用 $\sum_{x} d_{x} = O (n)$ ，总时间复杂度仍可界为 $O (n \log n)$ ，空间复杂度为 $O (n)$ 。

点击展开代码

cpp

int q[N], idx;
map<vector<int>, int> mp; // 待比较的所有树共享，处理中途不能清空
void dfs1(int x, int y) { // 以重心为根 dfs
    vector<int> tmp;
    for (auto u : p[x]) {
        if (u == y)
            continue;
        dfs1(u, x);
        tmp.push_back(q[u]);
    }
    sort(tmp.begin(), tmp.end());
    auto it = mp.find(tmp);
    if (it != mp.end()) {
        q[x] = it->second;
    } else {
        q[x] = ++idx;
        mp[tmp] = idx;
    }
}

注：若按后序分层收集所有整数序列，并使用适合整数键的基数排序统一编号，可以把确定性 AHU 规范化做到 $O (n)$ ；仅把 map 换成普通比较排序并不能自动得到该复杂度。

树哈希：

定义哈希函数 $h (x)$ ， $f (x) = (c + \sum_{y \in s o n (x)} h (f (y))) mod M$ 。对子树贡献求和使结果与儿子顺序无关，但也把整个儿子多重集压缩成了一个模意义下的和，因此不同多重集仍可能碰撞。

判断有根树 $T_{1}, T_{2}$ 同构时，比较 $f (r_{1}), f (r_{2})$ 即可。

下面给出单个 64 位自然溢出哈希的示例。u64 加法等价于模 $2^{64}$ ，随机 mask 只是在不同运行间改变映射，不能提供确定正确性：

点击展开代码

cpp

const u64 mask = std::chrono::steady_clock::now().time_since_epoch().count();
u64 shift(u64 x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}
u64 q[N];
void dfs1(int x, int y) { // 以重心为根 dfs
    q[x] = 1;
    for (auto u : p[x]) {
        if (u == y)
            continue;
        dfs1(u, x);
        q[x] += shift(q[u]);
    }
}

自然溢出仍然只是一路 64 位概率哈希，并不等价于双哈希。若需要降低随机碰撞概率，可以使用两个独立种子或模数的哈希；但可交换求和本身仍可能产生多重集结构碰撞，双哈也只能降低概率，不能给出数学上的零碰撞保证。面对可构造数据或要求确定正确的场景，应优先使用上面的 AHU 规范编码。

时间复杂度： $O (n)$ 。

与 AHU 算法相比：

AHU 是确定性规范编码，不存在概率哈希碰撞。
树哈希更容易实现、常数通常更小，但结论带有碰撞概率。
树哈希可以通过换根 dp， $O (n)$ 求出以所有节点为根时的哈希值。

有根树同构 ​

无根树同构 ​

AHU： ​

朴素做法： ​

优化： ​

树哈希： ​

有根树同构

无根树同构

AHU：

朴素做法：

优化：

树哈希：