树哈希
树哈希可以解决有根树的树同构问题(即随意交换儿子的顺序),同时可以快速进行换根。
设 \(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;
}
题意
给定 \(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;
}
|