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

· · 题解

首先简单讲解一下树哈希。

树哈希

树哈希和别的哈希没有本质的区别，只不过映射对象是树。一般我们的哈希函数如此设计。

f(x) = (c + \sum_{y \in xson} g(y)) \mod m

实际操作时，首项常数通常取一，模数采取自然溢出。

这里有模板题以及参考代码。

const ull mask = 1145141919810;
//mask取随机数即可
inline ull g(ull x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
  // g函数通常写法
    return x;
}
void dfs(int s, int fa) {
    Hash[s] = 1ull;//c取1
    for(int to: e[s]) {
        if(to == fa) continue;
        dfs(to, s);
        Hash[s] += g(Hash[to]);
    }
}

必要的前置知识讲完了，那我们回到题面。

在两棵同构的无根树上，我们思考什么是在编号改变后始终不变的。

没错就是重心的位置。而树的重心最多只有两个。于是我们只需要找出树的两个重心，记录以两个重心为根无根树的哈希值比较即可。

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
typedef unsigned long long ull;
using namespace std;
constexpr int N = 55;
const ull mask = mt19937_64(time(0))();
inline ull g(ull x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}
long long target, g1, g2, m, n, root, p, dp[N], dep[N], siz[N];
vector<int> e[N];
void init(int s, int fa) {
    dep[s] = dep[fa] + 1;
    dp[root] += dep[s];
    siz[s] = 1;
    for(register int to : e[s]) {
        if(to == fa) continue;
        init(to, s);
        siz[s] += siz[to];
    }
}
void dfs(int s, int fa) {
    for(register int to : e[s]) {
        if(to == fa) continue;
        dp[to] = dp[s] + n - siz[to] * 2;
        dfs(to, s);
    }
}
ull Hash(int s, int fa) {
    ull hash = 1ull;
    for(register int to : e[s]) {
        if(to == fa) continue;
        hash += g(Hash(to, s));
    }
    return hash;
}
map<pair<ull, ull>, int>mp;
int main() {
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> m;
    rep(i, 1, m) {
        cin >> n;
        g1 = g2 = 0;
        memset(dp, 0, sizeof dp);
        memset(dep, 0, sizeof dep);
        memset(siz, 0, sizeof siz);
        target = 1e18;
        rep(j, 1, 50) e[j].clear();
        rep(j, 1, n) {
            cin >> p;
            if(!p) {
                root = j;
                continue;
            }
            e[p].push_back(j);
            e[j].push_back(p);
        }
        init(root, 0);
        dfs(root, 0);
        rep(j, 1, n) {
            target = min(target, dp[j]);
        }
        rep(j, 1, n) {
            if(dp[j] == target) {
                if(g1) {
                    g2 = j;
                }
                else {
                    g1 = j;
                }
            }
        }
      //预处理出树的重心
        ull p1 = Hash(g1, 0);
        ull p2 = Hash(g2, 0);
        if(p1 > p2) {
            swap(p1, p2);
        }
        auto now = make_pair(p1, p2);
    //记录哈希值，存储进map即可
        if(mp[now]) {
            cout << mp[now] << '\n';
        }
        else {
            cout << i << '\n';
            mp[now] = i;
        }
    }
    return 0;
}