给两棵树设计可加的 64 位树哈希,换根 DP 求出 A 的 n 种根哈希存入集合,再逐个删掉 B 的叶子用 O(1) 撤销算出剩余哈希查表,取编号最小的叶子。
OJ: roj
题目 ID: 1695
难度:提高+/省选-
标签:哈希树换根DPpython
创建: 2026-10-07 16:01
更新: 2026-10-07 16:01
形式化题目
给定无根树
用
把
正解
思路
先想朴素做法为什么不行。 枚举每个叶子
所以要找一个能把整棵树的形状压成一个整数的指纹:指纹相同就认为同构。 这就是树哈希。
树哈希的设计。 固定一个根,让
其中
它是双射并具备雪崩性——输入差一位,输出看起来完全随机。指纹的两个要点:
- 总和里的每一项都先过
。 如果直接累加 , 那么"一个孩子的指纹恰好等于另一个孩子的两倍"这类结构巧合会让不同的孩子集合撞成同一个和; 过一遍 后,孩子贡献是伪随机的 64 位数,集合不同则和几乎必然不同。 同时这也避免了异或聚合的老毛病:两个相同的孩子异或后互相抵消,掩盖了"重复"这一结构事实。 - 乘上
这一项。 只累加孩子贡献的话,深度不同的树会撞车 (例如"一个孩子"与"一个孩子加一个空孩子"分不开),把子树大小也混进去就把形状和规模一起编码了。
哈希的可加性是本题的关键:因为聚合是求和,从"以
第一步:求出
割掉边
这里
第二步:枚举
叶子没有孩子,所以
为什么根不能随便取。 如果
以样例走一遍。
| 叶子 |
邻居 |
删掉 |
|
|---|---|---|---|
| 点 |
是 | ||
| 点 |
是 | ||
| 一条 |
否 |
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 16:01
# update_at: 2026-10-07 16:01
import sys
MASK = (1 << 64) - 1 # 所有哈希都在 64 位无符号内回绕,等价于 C++ 的 unsigned long long
GOLDEN = 0x9e3779b97f4a7c15 # splitmix64 的加性常数,先加它再混淆才不会丢掉输入的差异
type Graph = list[list[int]] # 邻接表:下标是点编号,值是该点的邻居列表
type IntArrays = tuple[list[int], list[int]] # 两个等长整型数组的配对(父亲/先序、子树大小/子树哈希等)
def mix(x: int) -> int:
"""splitmix64 收尾混淆:可逆地把整数打散成雪崩良好的 64 位伪随机值。"""
x = (x + GOLDEN) & MASK
x = ((x ^ (x >> 30)) * 0xbf58476d1ce4e5b9) & MASK
x = ((x ^ (x >> 27)) * 0x94d049bb133111eb) & MASK
return x ^ (x >> 31)
def rooted_order(g: Graph, root: int) -> IntArrays:
"""迭代 DFS,返回 (par, order):order 是先序,每个点的父亲都排在它前面。"""
par = [0] * len(g)
order: list[int] = []
stk = [root]
while stk:
u = stk.pop()
order.append(u)
for v in g[u]:
if v == par[u]:
continue # 树上只有父亲这一个邻居已经走过
par[v] = u
stk.append(v)
return par, order
def subtree_hash(g: Graph, par: list[int], order: list[int]) -> IntArrays:
"""自底向上求子树大小 sz 与子树哈希 f[u] = mix(sz[u]) + Σ mix(f[孩子])。"""
sz = [1] * len(g)
f = [0] * len(g)
for u in reversed(order):
for v in g[u]:
if v != par[u]:
sz[u] += sz[v]
f[u] += mix(f[v])
f[u] = (mix(sz[u]) + f[u]) & MASK
return sz, f
def reroot_hash(g: Graph, par: list[int], order: list[int], sz: list[int], f: list[int]) -> list[int]:
"""换根求 full[u]:整棵树以 u 为根时的哈希;树的点数就是 len(order)。"""
total = len(order)
mix_total = mix(total)
full = [0] * len(g)
full[order[0]] = f[order[0]] # 出发点没有"上方",full 就是子树哈希
for u in order:
for v in g[u]:
if v == par[u]:
continue
# 割掉边 (u, v) 后 u 那一侧(total - sz[v] 个点):从 full[u] 里摘掉 u 的大小项和 v 的贡献
up = (mix(total - sz[v]) + full[u] - mix_total - mix(f[v])) & MASK
full[v] = (mix_total + f[v] - mix(sz[v]) + mix(up)) & MASK
return full
def best_leaf(g_b: Graph, par_b: list[int], full_b: list[int], f_b: list[int], hash_a: set[int], n: int) -> int:
"""候选叶子里的最小编号:B 的叶子 x 删去后,B - x 的哈希落在 hash_a 里就算合法。"""
mix_b = mix(n + 1)
mix_n = mix(n)
# 删掉叶子 x:它没有孩子(f_b[x] = mix(1)),剩下的 n 个点以它唯一的邻居 par_b[x] 为根
rest_hash = {x: (full_b[par_b[x]] - mix_b + mix_n - mix(f_b[x])) & MASK
for x in range(1, n + 2) if len(g_b[x]) == 1}
return min(x for x, h in rest_hash.items() if h in hash_a)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
g_a: Graph = [[] for _ in range(n + 1)] # 树 A:编号 1..n
for _ in range(n - 1):
x, y = next(data), next(data)
g_a[x].append(y)
g_a[y].append(x)
g_b: Graph = [[] for _ in range(n + 2)] # 树 B:编号 1..n+1
for _ in range(n):
x, y = next(data), next(data)
g_b[x].append(y)
g_b[y].append(x)
if n == 1: # A 是单点树,B 是一条边,两个叶子都合法
print(1)
return
par_a, order_a = rooted_order(g_a, 1)
sz_a, f_a = subtree_hash(g_a, par_a, order_a)
# A 的 n 种根哈希:只要某棵 n 点树与 A 同构,它的哈希必落在这个集合里
hash_a = set(reroot_hash(g_a, par_a, order_a, sz_a, f_a))
# B 的根取度数 > 1 的点:否则根自己就是叶子,删掉它的情形会被漏掉(n >= 2 时必存在)
root_b = next(v for v in range(1, n + 2) if len(g_b[v]) > 1)
par_b, order_b = rooted_order(g_b, root_b)
sz_b, f_b = subtree_hash(g_b, par_b, order_b)
full_b = reroot_hash(g_b, par_b, order_b, sz_b, f_b)
print(best_leaf(g_b, par_b, full_b, f_b, hash_a, n))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 16:01
* update_at: 2026-10-07 16:01
*/
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 100005; // n <= 10^5,树 B 有 n + 1 <= 100001 个点,编号 1 .. n+1
int n; // 树 A 的点数(题面的 N)
vector<int> gA[MAXN]; // 树 A 的邻接表
vector<int> gB[MAXN]; // 树 B 的邻接表,点数 n + 1
// 一棵被"固定根"的树里,每个点的信息聚合成 node[u](先服务树 A,再复用来服务树 B)
struct Node {
int par; // 当前固定根意义下 u 的父亲,根的 par 为 0
int sz; // 以 u 为根的子树大小(点数)
ull sub; // u 子树的哈希:sub(u) = mix(sz(u)) + Σ mix(sub(孩子))
ull full; // 整棵树换成以 u 为根时的哈希
};
Node node[MAXN];
int order[MAXN]; // DFS 序,保证父亲排在儿子前面
int ordCnt; // DFS 序的长度,也就是当前被处理树的点数
ull rootA[MAXN]; // 树 A 在 n 个点分别作根时的整树哈希,升序排列,供二分查找
// splitmix64 的收尾混淆:把整数打散成雪崩良好的 64 位伪随机数
ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
// 无向边加进邻接表
void add_edge(vector<int> *g, int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
// 迭代式 DFS:求以 root 为根的 par 与"先父后子"的 order(深链也不会爆栈)
void dfs_order(vector<int> *g, int root) {
static int stk[MAXN];
int top = 0;
ordCnt = 0;
node[root].par = 0;
stk[top] = root;
top++;
while (top > 0) {
top--;
int u = stk[top];
order[ordCnt] = u;
ordCnt++;
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (v == node[u].par) continue; // 树上只有父亲这一个邻居已经走过
node[v].par = u;
stk[top] = v;
top++;
}
}
}
// 按 order 的逆序自底向上求子树大小与子树哈希
// 孩子哈希先过 mix 再相加,这样"去掉一个孩子"只需从和里减去它的贡献
void calc_subtree(vector<int> *g) {
for (int i = ordCnt - 1; i >= 0; i--) {
int u = order[i];
int s = 1; // 先算上自己这个点
ull h = 0; // 孩子贡献之和
for (int j = 0; j < (int)g[u].size(); j++) {
int v = g[u][j];
if (v == node[u].par) continue;
s += node[v].sz;
h += mix(node[v].sub);
}
node[u].sz = s;
node[u].sub = mix((ull)s) + h;
}
}
// 换根:整棵树共 total 个点,由 u 的 full 推出儿子 v 的 full
// 割掉边 (u,v) 后 u 那一侧的哈希(共 total - sz(v) 个点):
// up = mix(total - sz(v)) + (full(u) - mix(total) - mix(sub(v)))
// 括号里就是把 u 的大小项和儿子 v 的贡献摘掉,剩下的正是 u 朝其余方向的一切
// full(v) = mix(total) + (sub(v) - mix(sz(v))) + mix(up)
void calc_full(vector<int> *g, int total) {
ull mixTotal = mix((ull)total);
node[order[0]].full = node[order[0]].sub; // 出发点没有"上方",full 就等于子树哈希
for (int i = 0; i < ordCnt; i++) {
int u = order[i];
for (int j = 0; j < (int)g[u].size(); j++) {
int v = g[u][j];
if (v == node[u].par) continue;
ull up = mix((ull)(total - node[v].sz)) + node[u].full - mixTotal - mix(node[v].sub);
node[v].full = mixTotal + (node[v].sub - mix((ull)node[v].sz)) + mix(up);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int x, y;
scanf("%d %d", &x, &y);
add_edge(gA, x, y);
}
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
add_edge(gB, x, y);
}
if (n == 1) {
// 树 A 是单点树,树 B 只有一条边,删掉哪个叶子剩下的都是单点树
printf("1\n");
return 0;
}
// ---- 树 A:求出以每个点为根时的整树哈希,排序后备用 ----
dfs_order(gA, 1);
calc_subtree(gA);
calc_full(gA, n);
for (int u = 1; u <= n; u++) rootA[u] = node[u].full;
sort(rootA + 1, rootA + n + 1);
// ---- 树 B:n + 1 个点,取一个度数大于 1 的点当根(n >= 2 时一定存在) ----
int rootB = 1;
for (int v = 1; v <= n + 1; v++) {
if ((int)gB[v].size() > 1) {
rootB = v;
break;
}
}
dfs_order(gB, rootB);
calc_subtree(gB);
calc_full(gB, n + 1);
// 逐个检查 B 的叶子 x:设它的唯一邻居是 u,删掉 x 后以 u 为根的 n 点树哈希为
// full(u) - mix(n+1) + mix(n) - mix(sub(x))
// 叶子没有孩子,sub(x) 就是 mix(1),直接减掉这一份贡献即可
int ans = n + 2; // 题面保证有解,这是保险初值
ull mixB = mix((ull)(n + 1));
ull mixN = mix((ull)n);
for (int x = 1; x <= n + 1; x++) {
if ((int)gB[x].size() != 1) continue; // 只看叶子
int u = node[x].par; // 叶子唯一的邻居
ull h = node[u].full - mixB + mixN - mix(node[x].sub);
if (binary_search(rootA + 1, rootA + n + 1, h) && x < ans) ans = x;
}
printf("%d\n", ans);
return 0;
}复杂度
- 时间:树
与树 各做一次迭代 DFS( )、一次自底向上的子树统计( )、 一次自顶向下的换根( ),这些主体部分构成 。 最后把 的 个根哈希装入一个查询结构:Python 版用 set,插入与查询期望, 总时间期望 ;C++ 版为了避开 unordered_set的哈希风险改用排序数组 +binary_search,多一层的排序, 时实测 0.05 s,同样安全。 - 空间:邻接表
,加上父亲的父亲、子树大小、先序序列、子树哈希、根哈希五个长度为 的数组(C++ 里聚合成一个 Node node[MAXN]),共。 - 正确性边界:哈希相等是"同构"的必要条件,逆向依赖随机性——
两棵不同构的树碰巧哈希相等的概率约为
, 时全部比较的碰撞期望 远小于 ,可以认为不会发生。 - 与 C++ 解法的关系:
main.cpp是同一算法的 C++ 实现,用一个有序数组加binary_search代替 Python 的set,并用手写迭代 DFS 以避开深链的爆栈问题, 总体复杂度同为 / 期望 这一档。 - 特判:
时 只有 个点、 只有一条边, 删掉哪个叶子剩下的都是单点树,直接输出 (此时 无度大于 的点,换根根的选择会失效)。
总结
- 把形状压成指纹:无法直接比对的"树同构"问题,第一步总是设计一个整树哈希; 一旦有了哈希,"是否存在同构的树"就退化成一次集合查询。
- 哈希要选可撤销的聚合:本题用的是求和,于是换根与删叶子都只是"减掉一份贡献"这种
操作; 若用最小值、乘积之类不可逆的聚合,就无法做到这一点。 - 每一项先混淆再聚合:孩子贡献必须先过
再累加, 否则结构化巧合会让不同的孩子集合撞成同一个和; 也要混进指纹, 否则不同深度的形状会撞车。 - 无根树要比"所有根的指纹":只用某一个根的哈希判断同构会漏解,
所以要对
做换根求出 个根哈希全部入集合。 - 固定根不能取在答案上:
的根必须选度数大于 的点, 否则当答案恰好是根时,删叶子的公式无父可依。