跳转至

树哈希

树哈希可以解决有根树的树同构问题（即随意交换儿子的顺序），同时可以快速进行换根。

设 \(h(u)\) 表示 \(u\) 子树的哈希值。我们可以按照如下方式进行递推：

\[ h(u)=1+\sum_{v\in to[u]}\operatorname{shift}\bigl(h(v)\big) \]

其中 \(\operatorname{shift}\) 表示一种二进制位混合运算，一般如下：

ull seed = (mt19937_64){(random_device){}()}(); // 单次生成随机数
ull shift(ull x) {
    x ^= x << 2;
    x ^= x >> 3;
    x ^= x << 17;
    return x ^ seed;
}

P5043 【模板】树同构（[BJOI2015]树的同构）

题意

给定 \(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
 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
 98
 99
100
101
#include<iostream>
#include<random>
#include<ctime>
#include<map>
#define ull unsigned long long
using namespace std;
const int N = 55;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

void clear_Edge(int n) {
    ne = 0;
    for(int i = 1; i <= n; i++) head[i] = 0;
}

int t, n;
int sz[N], mxp[N] = {1024};
int rt;

ull hsh[N], seed = (mt19937_64){(random_device){}()}();

ull shift(ull x) {
    x ^= x << 2;
    x ^= x >> 3;
    x ^= x << 17;
    x ^= seed;
    return x;
}

void get_rt(int u, int fa) {
    sz[u] = 1;
    mxp[u] = 0;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        get_rt(v, u);
        sz[u] += sz[v];
        mxp[u] = max(mxp[u], sz[v]);
    }
    mxp[u] = max(mxp[u], n - sz[u]);
    if(mxp[u] < mxp[rt]) rt = u;
}

void dfs(int u, int fa) {
    hsh[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs(v, u);
        hsh[u] += shift(hsh[v]);
    }
    ++hsh[u];
}

ull calc() {
    if(n & 1) {
        return hsh[rt];
    } else {
        get_rt(rt, 0);
        for(int e = head[rt]; e; e = pool[e].next) {
            int v = pool[e].v;
            if(sz[v] == n / 2) return hsh[rt] ^ (hsh[v] + shift(hsh[rt] - shift(hsh[v])));
        }
        return hsh[rt];
    }
}

map<ull, int> mp;

int main() {

    cin >> t;
    for(int k = 1; k <= t; k++) {
        cin >> n;
        clear_Edge(n);
        for(int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if(x) {
                addEdge(x, i);
                addEdge(i, x);
            }
        }
        rt = 0;
        get_rt(1, 0);
        dfs(rt, 0);
        int &res = mp[calc()];
        if(res) cout << res << '\n';
        else cout << (res = k) << '\n';
    }

    return 0;
}