神奇的树

https://www.matiji.net/exam/dohomework/8235/2

题干

小码哥在花园中种了 $n$ 颗神奇的树，花园中的第 $i$ 颗树 $T_i$ 正好是无根树 $G$ 以 $i$ 节点为根所形成的有根树。（ $G$ 由输入给定）

小码哥想知道对于所有从 $1$ 到 $n$ 的 $i$ ， $T_i$ 与花园中的多少颗树同构，即集合 $\{T_j | 1 \leq j \leq n 且 T_j 与 T_i 同构\}$ 的大小？（ $T_i$ 与 $T_j$ 同构也可统计进答案）

两棵有根树 $T_1$ $T_2$ 同构当且仅当它们的大小相等，且存在一个顶点排列 $\sigma$ 使得在 $T_1$ 中 $i$ 是 $j$ 的祖先当且仅当在 $T_2$ 中 $\sigma(i)$ 是 $\sigma(j)$ 的祖先。

思路

注意时间限制 $3s$ 不是 $1s$ ， $n \leq 5e5$ ，大概是 $O(n \log n)$ 以下。

做法是树 hash，即对于一个树，将其编码成 hash。然后计算过程中是可以直接换根的，因此复杂度只有 $O(n)$。

树哈希的定义与计算方法

树哈希是一种将树结构编码成一个唯一哈希值的方法，它能够帮助我们快速判断两棵树是否同构。在同构的树中，节点的相对结构是相同的，但节点的编号可能不同。

树哈希的核心思想

我们通过递归地计算每个节点的哈希值 $val$ ，并结合子节点的哈希值来唯一确定一棵树的结构。
树哈希的定义包含以下几点：

1. 叶子节点的哈希值是一个固定值，通常初始化为 $c = 1$（可以理解为基本单元）。
2. 非叶子节点的哈希值由其所有子节点的哈希值通过某个函数组合得到。
3. 为了避免哈希冲突，通常使用一个扰动函数 $f(x)$ 对子节点的哈希值进行处理，使哈希值更加均匀分布。

具体计算方法

我们定义一个节点 $i$ 的哈希值 $val[i]$ 如下：

• 基础值 $c$：每个节点自身初始哈希值设为 1。

• 扰动函数 $f(x)$：用于对子节点的哈希值进行扰动，常用形式是：

  $$f(x) = x \oplus \text{随机数}$$

  其中 (\oplus) 表示按位异或，或者可以用 $x \times 31 + 7$ 等其他操作。
  这个函数的作用是让相同结构但不同子树排列的节点产生不同的中间哈希值，减少冲突。

• 节点哈希值的计算公式：
  对于一个节点 $i$，它的哈希值 $val[i]$ 等于自身基础值 $c$ 加上所有子节点的扰动后哈希值之和：

  $$val[i] = c + \sum_{j \in \text{子节点}(i)} f(val[j])$$

  其中 $f(val[j])$ 是子节点 $j$ 的哈希值经过扰动函数处理后的结果。

示例

考虑以下树结构：

自底向上计算哈希值

叶子节点（4 和 5）：

叶子节点没有子节点，它们的哈希值初始化为 $c = 1$ ， $val[4] = 1$ ， $val[5] = 1$ 。

节点 2（子节点为 4 和 5）：

$val[2]$ 由自身的初始值和两个子节点的哈希值决定：

$$val[2] = c + f(val[4]) + f(val[5])$$

假设扰动函数 $f(x) = x \times 31 + 7$ ，则：

$$f(1) = 1 \times 31 + 7 = 38$$

所以：

$$val[2] = 1 + 38 + 38 = 77$$

节点 3（叶子节点）：

$val[3] = c = 1$ 。

根节点 1（子节点为 2 和 3）：

$val[1]$ 由自身的初始值和两个子节点的哈希值决定：

$$val[1] = c + f(val[2]) + f(val[3])$$

已知 $val[2] = 77$ ， $val[3] = 1$ ，并计算：

$$f(77) = 77 \times 31 + 7 = 2394, \quad f(1) = 38$$

所以：

$$val[1] = 1 + 2394 + 38 = 2433$$

最终的哈希值：

节点 $i$	子节点	$val[i]$
4	无	1
5	无	1
2	4, 5	77
3	无	1
1	2, 3	2433

现在可以计算任意有根树的哈希了，不过下面可以通过换根加速计算。

换根

因为 $hash_0(root_0) = c + \sum_{j \in \text{旧树子节点}(root_0)} f(hash_1(j))$

而如果要换到一个相连的 $root_1$ ，那么 $hash_1(root_1) = c + \sum_{j \in \text{新树子节点}(root_1)} f(hash_1(j))$

注意，只有 $root_0$ 和 $root_1$ 的从属关系发生变化，因此其它子树的哈希不变，因此在新的树里，

$$hash_1(root_0) = c + \sum_{j \in \text{新树子节点}(root_0)} f(hash_1(j))= hash_0(root_0) - hash_0(root_1)$$

而 $hash_1(root_1) = hash_0(root_1) + hash_1(root_0)$

对于其它节点， $hash_0(i) = hash_1(i)$ 。同时，哈希规则不变，因此它总是代表树的结构——如果两个树的结构相同，那么它们的哈希值也相同。

这样程序实际复杂度在 $O(n)$ ，可能常数比较大。

代码

为了避免 hash 碰撞，把 $f$ 可以任性地取复杂一些。

#include <vector>
#include <functional>
#include <iostream>
#include <map>

using namespace std;
using ull = unsigned long long;

constexpr ull mask = 0x1234567898765432;

ull f(ull x) {
    x ^= mask;
    x ^= x << 7;
    x ^= x >> 13;
    x ^= x << 11;
    x ^= mask;
    return x;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> next(n, vector<int>());
    for(int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        next[a].push_back(b);
        next[b].push_back(a);
    }
    vector<ull> root_h(n, 0);
    vector<ull> tmp_h(n, 1);
    function<void(int,int)> dfs = [&](int cur, int from) {
        for(int n: next[cur]) {
            if(n != from) dfs(n, cur);
        }
        for(int n: next[cur]) {
            if(n == from) continue;
            tmp_h[cur] += f(tmp_h[n]);
        }
    };
    dfs(0, -1);
    function<void(int,int)> dfs2 = [&](int cur, int from) {
        root_h[cur] = tmp_h[cur];
        for(int n: next[cur]) {
            if(n == from) continue;
            ull next_hash = f(tmp_h[n]);
            tmp_h[cur] -= next_hash;
            tmp_h[n] += tmp_h[cur];
            dfs2(n, cur);
            tmp_h[n] -= tmp_h[cur];
            tmp_h[cur] += next_hash;
        }
    };
    dfs2(0, -1);
    map<ull, int> cnt;
    for(auto e: root_h) {
        ++cnt[e];
    }
    for(auto e: root_h) {
        cout << cnt[e] << endl;
    }
    return 0;
}