https://peehs-moorhsum.blog.uoj.ac/blog/7891
题目描述
对一棵树求 hash 值,以判断两棵树是否同构。有有根树和无根树两个版本。
solution
找一个随机函数 \(f\)(可以选 xor-shift),然后每个点的子树的哈希值如下计算:
\[h_u=1+\sum_{v}f(h_v) \]这是有根树的情况,对于无根树,1. 可以换根 dp 求出以任意点为根的 hash 值,然后取最小的;2. 找重心,求出重心为根的 hash 值,有两个重心取 hash 值较小的。
code
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
using word = unsigned long long;
mt19937_64 rng{random_device{}()};
const word mask = rng();
word shift(word x) {
x ^= mask;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x ^ mask;
}
int n, m;
basic_string<int> g[1000010];
word f[1000010], hsh[1000010];
word dfs(int u, int fa) {
word &ans = f[u] = 1;
for (int v : g[u]) if (v != fa) ans += shift(dfs(v, u));
return ans;
}
void dfs2(int u, int fa) {
for (int v : g[u]) if (v != fa) f[v] += shift(f[u] - shift(f[v])), dfs2(v, u);
}
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> m;
map<word, int> mp;
for (int t = 1; t <= m; t++) {
cin >> n;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1, x; i <= n; i++) {
cin >> x;
if (x) g[i] += x, g[x] += i;
}
dfs(1, 0);
dfs2(1, 0);
hsh[t] = *min_element(f + 1, f + n + 1);
if (!mp.count(hsh[t])) mp[hsh[t]] = t;
}
for (int i = 1; i <= m; i++) cout << mp[hsh[i]] << endl;
return 0;
}
标签:hash,int,shift,hsh,long,哈希,word,模板
From: https://www.cnblogs.com/caijianhong/p/18455143/template-tree-hash