最近笔记写太多封面用光了😭先空着吧

虽然之前说网络赛前再不写笔记了，但是学了一下发现还挺深刻，那还是写。

概述

有时我们会遇到判断两棵树是否同构的题目。对于这类问题，有一种确定性算法，名为AHU算法（ 得名自Aho, Hopcroft, Ullman三人名字首字母），借助基数排序，复杂度可以做到 $O(n)$ 。但是相对而言理解起来心智负担比较高，而本文介绍的树哈希则是一种将树的结构转成哈希值来判断树是否同构的算法，仅需要了解原理，即可在不借助任何模板的情况下写出。

不过凡事总有两面性，既然是哈希算法，那么就有错误的可能性。但是通过合理的哈希函数设计，我们能够把错误率控制在合理范围内，够用就好。

方法

事先说明，这种树哈希的做法只针对有根树，无根树的做法需要在其基础上进一步处理。

我们的树哈希做法基于一种多重集的哈希函数。以点 $u$ 为根的子树的哈希值，就是以其所有子节点 $v$ 为根的子树的哈希值构成的多重集的哈希值，即
$$
h_{u}=f({ h_{v} \mid v \in son(u)})
$$
其中 $h_{u}$ 表示以点 $u$ 为根的子树的哈希值，$f(S)$ 是多重集 $S$ 的哈希函数。

$f(S)$ 具体定义如下：
$$
f(S)=\left(C+\sum\limits_{x\in S}g(x)\right)\mod{m}
$$
其中 $C$ 是常数，一般选取 $1$ 即可，$m$ 是模数，可以自然溢出，也可以选取大质数。$g(x)$ 是某种整数到整数的映射，我们使用 xorshift 或 splitmix64 等非多项式函数均可。为了防止被卡哈希，可以给 xorshift 前后异或一个随机常量，或给 splitmix64 之前加一个随机常量。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
u64 h[N];

const u64 mask = mt19937_64(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 splitmix64(u64 x) {
    x += mask;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

void dfs(int u, int p) {
    h[u] = 1;
    for (int v : e[u]) {
        if (v == p) continue;
        dfs(v, u);
        h[u] += shift(h[v]);
    }
}

以上是有根树做法，对于无根树怎么处理？

我们选取的这种哈希函数的形式可以很方便的做换根DP。于是我们可以再次DFS，通过换根DP求出每个点为根时的哈希函数。这 $n$ 个哈希函数值本身又是一个多重集，我们对这个多重集再做一次哈希，将其当做整个无根树的哈希值即可。

另一种方法是，由于一棵树上最多只有两个重心，我们可以求出重心，以重心为根求对应的哈希函数值，如果有两个重心就统一保留较大/较小的哈希值，将其作为整个无根树的哈希值。

只要能够保证树同构的情况下获得的哈希值一样，合理的方法均可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
u64 f[N], h[N];

const u64 mask = mt19937_64(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 splitmix64(u64 x) {
    x += mask;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

void dfs1(int u, int p) {
    f[u] = 1;
    for (int v : e[u]) {
        if (v == p) continue;
        dfs1(v, u);
        f[u] += shift(f[v]);
    }
}

void dfs2(int u, int p) {
    for (int v : e[u]) {
        if (v == p) continue;
        h[v] = f[v] - shift(g[u] - shift(f[v]));
        dfs2(v, u);
    }
}

void solve() {
    // ...
    // 读入数据
    dfs1(1, 0); // 以 1 为根先跑一次 dfs
    h[1] = f[1]; 
    dfs2(dfs2, 1, 0); // 换根 dp
    u64 hash = 0; // 整棵树的哈希值
    for (int i = 1; i <= n; ++i) hash += h[i];
    // ...
}

例题

UOJ #763. 树哈希

模板题，有根树的树哈希，以 $1$ 为根做树哈希，同时统计哈希值的种类数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

const u64 mask = mt19937_64(time(nullptr))();

u64 splitmix64(u64 x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

u64 xorshift(u64 x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<u64> h(n + 1);
    set<u64> st;
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    auto dfs = [&](auto&& dfs, int u, int f) -> void {
        h[u] = 1;
        for (int v : e[u]) {
            if (v == f) continue;
            dfs(dfs, v, u);
            h[u] += splitmix64(h[v]);
        }
        st.insert(h[u]);
    };
    dfs(dfs, 1, 0);
    cout << st.size() << "\n";
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

P5043 【模板】树同构

无根树的树哈希，按照上述做法求出哈希值进行判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

u64 splitmix64(u64 x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

void solve() {
    int m;
    cin >> m;
    map<u64, int> mp;
    for (int i = 1; i <= m; ++i) {
        int n, rt;
        cin >> n;
        vector<vector<int>> e(n + 1);
        vector<u64> f(n + 1), g(n + 1);
        for (int j = 1, x; j <= n; ++j) {
            cin >> x;
            if (!x) rt = j;
            else e[x].push_back(j);
        }
        auto dfs1 = [&](auto&& dfs1, int u) -> void {
            f[u] = 1;
            for (int v : e[u]) {
                dfs1(dfs1, v);
                f[u] += splitmix64(f[v]);
            }
        };
        auto dfs2 = [&](auto&& dfs2, int u) -> void {
            for (int v : e[u]) {
                g[v] = f[v] + splitmix64(g[u] - splitmix64(f[v]));
                dfs2(dfs2, v);
            }
        };
        dfs1(dfs1, rt);
        g[rt] = f[rt];
        dfs2(dfs2, rt);
        u64 hash = 0;
        for (int i = 1; i <= n; ++i) hash += splitmix64(g[i]);
        if (!mp.contains(hash)) mp[hash] = i;
        cout << mp[hash] << "\n";
    }
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

3rd Ucup S30 K. Vortex

通信题，程序连续运行两次，每次给定一棵树，前后两次的数据保证树的结构相同，但编号会被打乱，每次输出一个排列 $p_{1},p_{2},\cdots,p_{n}$，需要保证两次的输出中，$(p_i,p_j)$ 之间连通当且仅当 $(q_i,q_j)$ 之间连通。

我们选定一种策略使得每次输出的点的编号排列都按照相同的顺序即可，这个顺序依靠树的形态来指定。求出每个点为根时的哈希值，首先输出哈希值最小的那个点，沿这个点进行DFS，每次将其子节点按照哈希值的大小进行排序，按照从小到大的顺序进行遍历，这样就能保证同样的结构按照同样的顺序进行遍历。

通信题会连续运行两次，这两次获得的随机数不同！因此常量需要直接指定，而不能使用随机数生成器！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

const u64 mask = 1145141919810;

u64 shift(u64 x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

u64 splitmix64(u64 x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<u64> f(n + 1), g(n + 1);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    auto dfs1 = [&](auto&& dfs1, int u, int p) -> void {
        f[u] = 1;
        for (int v : e[u]) {
            if (v == p) continue;
            dfs1(dfs1, v, u);
            f[u] += splitmix64(f[v]);
        }
    };
    auto dfs2 = [&](auto&& dfs2, int u, int p) -> void {
        for (int v : e[u]) {
            if (v == p) continue;
            g[v] = f[v] + splitmix64(g[u] - splitmix64(f[v]));
            dfs2(dfs2, v, u);
        }
    };
    dfs1(dfs1, 1, 0);
    g[1] = f[1];
    dfs2(dfs2, 1, 0);
    vector<int> p(n);
    iota(all(p), 1);
    ranges::sort(p, [&](auto x, auto y) {
        return g[x] < g[y];
    });
    auto dfs3 = [&](auto&& dfs3, int u, int p) -> void {
        cout << u << " ";
        vector<int> a;
        for (int v : e[u]) {
            if (v == p) continue;
            a.push_back(v);
        }
        ranges::sort(a, [&](auto x, auto y) { return g[x] < g[y]; });
        for (int v : a) {
            dfs3(dfs3, v, u);
        }
    };
    dfs3(dfs3, p[0], 0);
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

结语

本文疑似就是把Wiki整理了一遍（

参考资料

OI Wiki - 树哈希

peehs_moorhsum的博客 - 一种好写且卡不掉的树哈希