跳转至

树哈希

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

\(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\) 棵树,请将它们按无根树的同构划分为若干等价类。

对于无根树,我们先找到重心,然后记重心的哈希值为树的哈希值。如果有两个重心,将它们的哈希值异或起来即可。

代码
#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;
}