目录
写在前面
vp 的时候用到了于是来学一下。
好水。
抱歉了 AHU，但是树哈希它实在是太好写了。
树同构定义
有根树同构
对于两棵有根树 \(T_1(V_1,E_1,r_1)\) 和 \(T_2(V_2,E_2,r_2)\)，如果存在一个双射 \(\varphi: V_1 \rightarrow V_2\)，使得
\[\forall u,v \in V_1,(u,v) \in E_1 \iff (\varphi(u),\varphi(v)) \in E_2 \]且 \(\varphi(r_1)=r_2\) 成立，那么称有根树 \(T_1(V_1,E_1,r_1)\) 和 \(T_2(V_2,E_2,r_2)\) 同构。
无根树同构
对于两棵无根树 \(T_1(V_1,E_1)\) 和 \(T_2(V_2,E_2)\)，如果存在一个双射 \(\varphi: V_1 \rightarrow V_2\)，使得
\[\forall u,v \in V_1,(u,v) \in E_1 \iff (\varphi(u),\varphi(v)) \in E_2 \]成立，那么称无根树 \(T_1(V_1,E_1)\) 和 \(T_2(V_2,E_2)\) 同构。
简单的说就是，如果能够通过把树 \(T_1\) 的所有节点重新标号，使得树 \(T_1\) 和树 \(T_2\) 完全相同，那么称这两棵树同构。
树哈希
有根树
一种常用的好写的构造方法。
记 \(h_u\) 表示以 \(u\) 为根的子树的哈希值，记 \(f\) 为对多重集的哈希函数。
则可定义：
\[h_u = f(\{ h_v | v\in \operatorname{son}(u) \}) \]实现时常采用如下的哈希函数：
\[f(S) = \left( c + \sum_{x\in S} g(x) \right)\bmod m \]其中：
- \(c\) 为一常数，一般取 1 即可。
- \(m\) 为模数。
- \(g\) 为整数到整数的映射，代码中使用了
xor shift算法。
无根树
发现上述哈希值的定义方式天然支持换根操作。
于是可以考虑换根 DP 求得以所有节点为根的树的哈希值，再进行多重集哈希即得无根树的哈希值。
不过对于两棵无根树，更进一步地可观察得到一些性质：
- 它们的重心数量一定相等。
- 以重心为根的有根树一一对应。
于是可以考虑先求重心，构造出以重心为根的有根树哈希后比较哈希值，正确性有所上升。
AHU 算法
咕咕~
例题
UOJ #763. 树哈希
给定一棵以点 \(1\) 为根的树，你需要输出这棵树中最多能选出多少个互不同构的子树。
两棵有根树 \(T_1\)、\(T_2\) 同构当且仅当他们的大小相等，且存在一个顶点排列 \(\sigma\) 使得在 \(T_1\) 中 \(i\) 是 \(j\) 的祖先当且仅当在 \(T_2\) 中 \(\sigma(i)\) 是 \(\sigma(j)\) 的祖先。
\(1\le n\le 10^6\)。
5S，512MB。
有根树同构板题。
偷懒写了自然溢出。
为了不被叉掉，代码中使用了基于 C++11 特性的 std::chrono::steady_clock::now().time_since_epoch().count() 生成随机数。
//树哈希
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
const int kN = 1e6 + 10;
const int kM = kN << 1;
//=============================================================
int n, edgenum, head[kN], v[kM], ne[kM];
ULL f[kN], mask = std::chrono::steady_clock::now().time_since_epoch().count();
std::set<ULL> subtree;
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
ULL trans(ULL x_) {
x_ ^= mask;
x_ ^= x_ << 13ll;
x_ ^= x_ >> 7ll;
x_ ^= mask;
return x_;
}
void Dfs(int u_, int fa_) {
f[u_] = 1;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs(v_, u_);
f[u_] += trans(f[v_]);
}
subtree.insert(f[u_]);
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i < n; ++ i) {
int u_, v_; std::cin >> u_ >> v_;
Add(u_, v_), Add(v_, u_);
}
Dfs(1, 0);
std::cout << subtree.size();
return 0;
}
SP7826 - TREEISO - Tree Isomorphism
\(T\) 组数据，每组数据给定两棵大小为 \(n\) 的无根树，判断它们是否同构。
\(1\le T\le 400\)，\(1\le \sum n\le 10^5\)。
261ms，1.46GB。
SPOJ 一如既往的诡异时空限制。
无根树同构板题。
考虑换根 DP 求得以所有节点为根的树的哈希值，再进行多重集哈希即得无根树的哈希值。
//树哈希
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, edgenum, head[kN], v[kM], ne[kM];
ULL f[kN], g[kN], mask = std::chrono::steady_clock::now().time_since_epoch().count();
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Init() {
std::cin >> n;
edgenum = 0;
for (int i = 1; i <= 2 * n; ++ i) {
head[i] = f[i] = g[i] = 0;
}
}
ULL trans(ULL x_) {
x_ ^= mask;
x_ ^= x_ << 13ll;
x_ ^= x_ >> 7ll;
x_ ^= mask;
return x_;
}
void Dfs1(int u_, int fa_) {
f[u_] = 1;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs1(v_, u_);
f[u_] += trans(f[v_]);
}
}
void Dfs2(int u_, int fa_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
g[v_] = f[v_] + trans(g[u_] - trans(f[v_]));
// LL newf = f_ + f[u_] - trans(f[v_]);
Dfs2(v_, u_);
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Init();
for (int i = 1; i < n; ++ i) {
int u_, v_; std::cin >> u_ >> v_;
Add(u_, v_), Add(v_, u_);
}
for (int i = 1; i < n; ++ i) {
int u_, v_; std::cin >> u_ >> v_;
Add(u_ + n, v_ + n), Add(v_ + n, u_ + n);
}
Dfs1(1, 0), Dfs1(n + 1, 0);
g[1] = f[1], g[n + 1] = f[n + 1];
Dfs2(1, 0), Dfs2(n + 1, 0);
ULL sum[2] = {0};
for (int i = 1; i <= n; ++ i) {
sum[0] += trans(g[i]);
sum[1] += trans(g[i + n]);
}
std::cout << (sum[0] == sum[1] ? "YES\n" : "NO\n");
}
return 0;
}
P5043 【模板】树同构（[BJOI2015]树的同构）
同样无根树同构板题。
//树哈希
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int m, n, edgenum, head[kN], v[kM], ne[kM];
ULL f[kN], g[kN], mask = std::chrono::steady_clock::now().time_since_epoch().count();
std::map<ULL, int> tree;
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Init() {
std::cin >> n;
edgenum = 0;
for (int i = 1; i <= n; ++ i) {
head[i] = f[i] = g[i] = 0;
}
}
ULL trans(ULL x_) {
x_ ^= mask;
x_ ^= x_ << 13ll;
x_ ^= x_ >> 7ll;
x_ ^= mask;
return x_;
}
void Dfs1(int u_, int fa_) {
f[u_] = 1;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs1(v_, u_);
f[u_] += trans(f[v_]);
}
}
void Dfs2(int u_, int fa_) {
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
g[v_] = f[v_] + trans(g[u_] - trans(f[v_]));
Dfs2(v_, u_);
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> m;
for (int id = 1; id <= m; ++ id) {
Init();
for (int i = 1; i <= n; ++ i) {
int fa; std::cin >> fa;
if (fa == 0) continue;
Add(fa, i), Add(i, fa);
}
Dfs1(1, 0), g[1] = f[1], Dfs2(1, 0);
ULL sum = 0;
for (int i = 1; i <= n; ++ i) sum += trans(g[i]);
if (!tree.count(sum)) tree[sum] = id;
std::cout << tree[sum] << "\n";
}
return 0;
}
写在最后
参考：
标签：std,同构,int,笔记,fa,哈希,根树 From： https://www.cnblogs.com/luckyblock/p/18140075