树哈希
-
用于解决树同构问题
-
树同构
对于两个树 \(T_1\) 和 \(T_2\)，如果能够把树 \(T_1\) 的所有点重新标号，使得树 \(T_1\) 和树 \(T_2\) 完全相同，那么这两个树是同构的。也就是说，它们具有相同的形态
-
-
方法
-
将子树大小等信息进行哈希
-
用 unsigned long long 自然溢出
-
-
法一：$ Xor $ _ $ shift $
- 貌似不太好进行换根
# define i64 long long
unsigned i64 Xor_shift(unsigned i64 x){
x ^= x >> 13;
x ^= x << 7;
x ^= x >> 17;
return x;
}
void Dfs(int x){
hsh[x] = 1;
for(auto i : e[x]){
Dfs(i);
hsh[x] += Xor_shift(hsh[i]);
}
}
-
法二：对 $ size $ 哈希
-
用质数表作为哈希函数
-
换根大法好，用于无根树树哈希
-
也可以以重心为根进行树哈希，只需要做1或2次
-
void Dfs(int x){
si[x] = 1;
hsh[x] = 1;
for(auto i : e[x]){
Dfs(i);
si[x] += si[i];
hsh[x] += hsh[i] * prime[si[i] - 1];
}
}
//换根
void Dfs2(int x){
for(auto i : e[x]){
f[i] = (f[x] - hsh[i] * prime[si[i] - 1]) * prime[n - si[i] - 1] + hsh[i];
Dfs2(i);
}
}
P5043 【模板】树同构（[BJOI2015]树的同构）
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int MOD = 998244353;
const int N = 1000 + 10;
int m;
int n, fa, si[N];
unsigned int hsh[N], f[N];
vector <int> e[N];
vector <unsigned int> temp;
map <vector <unsigned int>, int> rec;
bool p[N];
vector <int> prime;
void Euler(){
int k = 1000;
for(int i = 2; i <= k; i++){
if(p[i] == 0){
prime.push_back(i);
}
for(auto j : prime){
if(i * j > k){
break;
}
p[i * j] = 0;
if(i % j == 0){
break;
}
}
}
}
void Dfs(int x){
si[x] = 1;
for(auto i : e[x]){
Dfs(i);
si[x] += si[i];
hsh[x] += hsh[i] * prime[si[i] - 1];
}
}
void Dfs2(int x){
for(auto i : e[x]){
f[i] = (f[x] - hsh[i] * prime[si[i] - 1]) * prime[n - si[i] - 1] + hsh[i];
Dfs2(i);
}
}
signed main(){
// freopen("1.in", "r", stdin);
Euler();
cin >> m;
for(int i = 1; i <= m; i++){
int rt = 0;
cin >> n;
for(int j = 1; j <= n; j++){
hsh[j] = 1, f[j] = 0, si[j] = 0;
e[j].clear();
}
for(int j = 1; j <= n; j++){
cin >> fa;
if(fa == 0){
rt = j;
}else{
e[fa].push_back(j);
}
}
Dfs(rt);
f[rt] = hsh[rt];
Dfs2(rt);
temp.clear();
sort(f + 1, f + 1 + n);
for(int j = 1; j <= n; j++){
temp.push_back(f[j]);
}
if(rec[temp] == 0){
rec[temp] = i;
}
cout << rec[temp] << "\n";
}
}