树的同构（树哈希）

树哈希是一种将树映射成整数的方法，常用于判断两棵树是否同构。

树哈希

我们有时需要判断一些树是否同构。这时，选择恰当的哈希方式来将树映射成一个便于储存的哈希值（一般是 32 位或 64 位整数）是一个优秀的方案。

树哈希定义在有根树上。判断无根树同构的时候，可以比较重心为根的哈希值，或者比较每个点为根的哈希值（树的大小相同，对哈希值排序后比较）。

以下是一种树哈希的构造方式：

\[f_x = 1 + \sum_{son_x}^y f_y \times prime(size_y)\]

$f_x$ 表示以 $x$ 为根的子树的哈希值，$son_x$ 表示 $x$ 的儿子集合，$size_y$ 表示以 $y$ 为根的子树的大小，$prime(i)$ 表示第 $i$ 个质数.

例题

P5043 模板 树同构

模板题，无根树的同构判断，把每个点为根的哈希值都算一下，排序之后比较。

#include <bits/stdc++.h>
#define pb push_back
const int maxP = 500;
int n, m, x, minp[maxP + 5], sz[55];
bool vis[55];
std::vector<int> to[55], hash[55], primes;
int dfs(int x) {
    int res = 1;
    vis[x] = 1;
    for (auto &nxt : to[x]) {
        if (!vis[nxt]) {
            res += dfs(nxt);
        }
    }
    return sz[x] = res + 1;
}
int tree_hash(int x) {
    int res = 0;
    vis[x] = 1;
    for (auto &nxt : to[x]) {
        if (!vis[nxt]) {
            res += primes[sz[nxt]] * tree_hash(nxt);
        }
    }
    return res + 1;
}
bool eq(std::vector<int> x, std::vector<int> y) {
    if (x.size() != y.size()) {
        return 0;
    }
    int sz = x.size();
    for (int i = 0; i < sz; i++) {
        if (x[i] != y[i]) {
            return 0;
        }
    }
    return 1;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    for (int i = 2; i <= maxP; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.pb(i);
        }
        for (auto &p : primes) {
            if (p * i > maxP) {
                break;
            }
            minp[p * i] = p;
            if (minp[i] == p) {
                break;
            }
        }
    }
    std::cin >> m;
    for (int i = 1; i <= m; i++) {
        std::cin >> n;
        for (int j = 1; j <= n; j++) {
            to[j].resize(0);
        }
        for (int j = 1; j <= n; j++) {
            std::cin >> x;
            if (x) {
                to[j].pb(x), to[x].pb(j);
            }
        }
        for (int j = 1; j <= n; j++) {
            memset(sz, 0, sizeof(sz));
            memset(vis, 0, sizeof(vis));
            dfs(j);
            memset(vis, 0, sizeof(vis));
            hash[i].pb(tree_hash(j));
            for (int j = 1; j <= n; j++) {
                //    std::cerr << sz[j] << " ";
            }
            // std::cerr << std::endl;
        }
        std::sort(hash[i].begin(), hash[i].end());
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= i; j++) {
            if (eq(hash[i], hash[j])) {
                std::cout << j << std::endl;
                break;
            }
        }
    }
    return 0;
}

G. Subgraph Isomorphism

判断一个连通无向图是不是一颗基环树，且环上的子树依次为 “ababab”或“aaaaaa”。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxN = 1e5, mod2 = 1e9 + 7, P = 1e7, hx = 76773, mod1 = 998244353;
int n, m, found, minp[P + 5], sz[maxN + 5], seed[maxN + 5], deg[maxN + 5];
vector<int> to[maxN + 5], loop, primes;
vector<pair<int, int>> t_hash;
bool vis[maxN + 5];
void dfs(int x) {
    vis[x] = 1;
    loop.pb(x);
    for (auto it : to[x]) {
        if (!vis[it]) {
            dfs(it);
        }
    }
}
int dfs2(int x) {
    int res = 1;
    vis[x] = 1;
    for (auto it : to[x]) {
        if (!vis[it]) {
            res += dfs2(it);
        }
    }
    return sz[x] = res;
}
pair<int, int> dfs3(int x) {
    int res1 = 0;
    int res2 = 0;
    vis[x] = 1;
    for (auto it : to[x]) {
        if (!vis[it]) {
            res1 = (res1 + primes[sz[it]] * dfs3(it).first) % mod1;
            res2 = (res2 + seed[sz[it]] * dfs3(it).second) % mod2;
        }
    }
    res2 = (res2 + 11451 * sz[x]) % mod2;
    return make_pair(res1 + 1, res2);
}
void solve() {
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        vis[i] = sz[i] = deg[i] = 0;
        to[i].resize(0);
    }
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        to[u].pb(v);
        to[v].pb(u);
        deg[u]++, deg[v]++;
    }
    if (m == n - 1) {
        cout << "YES\n";
        return;
    }
    if (m > n) {
        cout << "NO\n";
        return;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            q.push(i);
            vis[i] = 1;
        }
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto it : to[x]) {
            deg[it]--;
            if (!vis[it] && deg[it] == 1) {
                vis[it] = 1;
                q.push(it);
            }
        }
    }
    int st;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            st = i;
            break;
        }
    }
    loop.resize(0);
    dfs(st);
    for (int i = 0; i <= n; i++) {
        vis[i] = 0;
    }
    for (int i = 0; i < loop.size(); i++) {
        vis[loop[i]] = 1;
    }
    for (int i = 0; i < loop.size(); i++) {
        dfs2(loop[i]);
    }
    t_hash.resize(0);
    for (int i = 0; i <= n; i++) {
        vis[i] = 0;
    }
    for (int i = 0; i < loop.size(); i++) {
        vis[loop[i]] = 1;
    }
    for (int i = 0; i < loop.size(); i++) {
        t_hash.pb(dfs3(loop[i]));
    }
    for (int i = 0; i < t_hash.size(); i++) {
        if (t_hash[i] != t_hash[(i + 2) % t_hash.size()]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 2; i <= P; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.pb(i);
        }
        for (auto &p : primes) {
            if (p * i > P) {
                break;
            }
            minp[p * i] = p;
            if (minp[i] == p) {
                break;
            }
        }
    }
    seed[0] = 1;
    for (int i = 1; i <= maxN; i++) {
        seed[i] = seed[i - 1] * hx % mod2;
    }
    int _;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}