独特的树叶

GitHub跳转原题关系图返回列表

给两棵树设计可加的 64 位树哈希,换根 DP 求出 A 的 n 种根哈希存入集合,再逐个删掉 B 的叶子用 O(1) 撤销算出剩余哈希查表,取编号最小的叶子。

OJ: roj

题目 ID: 1695

难度:提高+/省选-

标签:哈希树换根DPpython

创建: 2026-10-07 16:01

更新: 2026-10-07 16:01

形式化题目

给定无根树 AA(nn 个点,编号 1…n1 \dots n)与无根树 BB(n+1n+1 个点,编号 1…n+11 \dots n+1)。 已知 BB 恰好在 AA 的基础上加入一个叶子并把编号打乱得到,求这个多余叶子在 BB 中的编号; 若有多个合法叶子,输出编号最小的那个。

用 L(B)L(B) 表示 BB 的叶子集合(度为 11 的点)。对 x∈L(B)x \in L(B),记 B−xB - x 为删掉 xx 及其唯一邻接边后剩下的 nn 点树。所求即

min⁡{ x∈L(B)  :  B−x 与 A 同构 }.\min \{\, x \in L(B) \;:\; B - x \text{ 与 } A \text{ 同构} \,\}.

把 xx 从 BB 中删去后,剩下一棵 nn 点树。判断"两棵无根树是否同构"是本题唯一的难点: 树的形状千变万化,逐点比较的朴素做法无从下手,而 n⩽105n \leqslant 10^5 又不允许枚举删哪条叶边之后 再做一遍 O(n)O(n) 的带根的逐一比对。

正解

思路

先想朴素做法为什么不行。 枚举每个叶子 xx、删掉它,再判断剩下的树是否与 AA 同构。 "判断两棵无根树是否同构"本身就是个不平凡的问题;如果老老实实做, 就得把"以每个点为根"的 nn 种形态都与 AA 的 nn 种形态逐一递归比对, 光是单个叶子的判定就已经超时,更不用说枚举 O(n)O(n) 个叶子。

所以要找一个能把整棵树的形状压成一个整数的指纹:指纹相同就认为同构。 这就是树哈希。

树哈希的设计。 固定一个根,让 uu 的指纹只依赖它的孩子:

f(u)=mix(siz(u))+∑v 是 u 的孩子mix(f(v)), f(u) = \mathrm{mix}\big(\mathrm{siz}(u)\big) + \sum_{v \text{ 是 } u \text{ 的孩子}} \mathrm{mix}\big(f(v)\big),

其中 mix\mathrm{mix} 取 splitmix64 的收尾混淆:

mix(x)=splitmix64 finalizer(x),\mathrm{mix}(x) = \text{splitmix64 finalizer}(x),

它是双射并具备雪崩性——输入差一位,输出看起来完全随机。指纹的两个要点:

  1. 总和里的每一项都先过 mix\mathrm{mix}。 如果直接累加 f(v)f(v), 那么"一个孩子的指纹恰好等于另一个孩子的两倍"这类结构巧合会让不同的孩子集合撞成同一个和; 过一遍 mix\mathrm{mix} 后,孩子贡献是伪随机的 64 位数,集合不同则和几乎必然不同。 同时这也避免了异或聚合的老毛病:两个相同的孩子异或后互相抵消,掩盖了"重复"这一结构事实。
  2. 乘上 siz\mathrm{siz} 这一项。 只累加孩子贡献的话,深度不同的树会撞车 (例如"一个孩子"与"一个孩子加一个空孩子"分不开),把子树大小也混进去就把形状和规模一起编码了。

哈希的可加性是本题的关键:因为聚合是求和,从"以 uu 为根"切换到"以 uu 的儿子 vv 为根" 时,只需从和里减去 mix(f(v))\mathrm{mix}(f(v))、再加上 vv 上方那部分的贡献,不需要重新 DFS。

第一步:求出 AA 的所有根哈希。 无根树的同构判断不能只看某一个根, 必须看"以任意点作根"的全套指纹。先固定以 11 为根求 ff,再做换根:

割掉边 (u,v)(u, v),设整棵树共 NN 个点,则 uu 那一侧有 N−siz(v)N - \mathrm{siz}(v) 个点。 把 uu 的指纹里"uu 自身大小项"和"vv 的贡献"一起摘掉,剩下的是 uu 朝其他所有方向的部分, 把它并入 N−siz(v)N - \mathrm{siz}(v) 这个新的大小项,就得到 uu 侧的指纹:

up=mix(N−siz(v))+full(u)−mix(N)−mix(f(v)), \mathrm{up} = \mathrm{mix}\big(N - \mathrm{siz}(v)\big) + \mathrm{full}(u) - \mathrm{mix}(N) - \mathrm{mix}\big(f(v)\big),
full(v)=mix(N)+(f(v)−mix(siz(v)))+mix(up). \mathrm{full}(v) = \mathrm{mix}(N) + \Big(f(v) - \mathrm{mix}\big(\mathrm{siz}(v)\big)\Big) + \mathrm{mix}(\mathrm{up}).

这里 full(u)\mathrm{full}(u) 是以 uu 为根的整棵树指纹,full(v)\mathrm{full}(v) 是以 vv 为根的整棵树指纹; 递推只在自顶向下的 DFS 序上做一遍,因为算 full(v)\mathrm{full}(v) 时 uu 的结果已经就绪。 把 AA 的 nn 个 full\mathrm{full} 值全部插入一个集合 SS。

第二步:枚举 BB 的叶子并在 O(1)O(1) 内算出删完后的指纹。 对 BB 同样求 fBf_B 与 fullB\mathrm{full}_B(注意 BB 有 n+1n+1 个点)。取 BB 的一个叶子 xx, 设唯一邻居为 uu。删掉 xx 后,剩下的 nn 点树以 uu 为根时的指纹就是 “fullB(u)\mathrm{full}_B(u) 摘掉自身大小项、去掉 xx 的贡献、再按 nn 个点重算大小项”:

H(x)=fullB(u)−mix(n+1)+mix(n)−mix(fB(x)). H(x) = \mathrm{full}_B(u) - \mathrm{mix}(n+1) + \mathrm{mix}(n) - \mathrm{mix}\big(f_B(x)\big).

叶子没有孩子,所以 fB(x)=mix(1)f_B(x) = \mathrm{mix}(1) 只贡献一项,直接减掉即可。 若 H(x)∈SH(x) \in S,则 B−xB - x 与 AA 同构,xx 是候选答案;所有候选中取编号最小的。

为什么根不能随便取。 如果 BB 的固定根本身就是个叶子,那么当答案恰好是这个根时, H(x)H(x) 无从计算(根没有父亲,也没有"上方")。所以取 BB 的一个度数大于 11 的点作根, n⩾2n \geqslant 2 时 BB 有 n+1⩾3n+1 \geqslant 3 个点,这样的点一定存在; 这样每个叶子都有确定的父亲,删它的公式始终可用。

以样例走一遍。 n=5n = 5,AA 的边为 1 ⁣− ⁣2,2 ⁣− ⁣3,1 ⁣− ⁣4,1 ⁣− ⁣51\!-\!2, 2\!-\!3, 1\!-\!4, 1\!-\!5, 形状是"中心 11 挂三叉,其中一叉再延伸一个点";BB 的边为 1 ⁣− ⁣2,2 ⁣− ⁣3,3 ⁣− ⁣4,4 ⁣− ⁣5,3 ⁣− ⁣61\!-\!2, 2\!-\!3, 3\!-\!4, 4\!-\!5, 3\!-\!6。 BB 的度为 11 的点是 1,5,61, 5, 6。设 BB 取点 22 为根,逐个检查:

叶子 xx 邻居 uu 删掉 xx 后 B−xB-x 的形状(不看编号) H(x)∈SH(x) \in S?
11 22 点 33 挂 2,4,62, 4, 6;44 再挂一个叶子 是
55 44 点 33 挂 2,4,62, 4, 6;22 再挂一个叶子 是
66 33 一条 55 点长链(没有度 33 的点) 否

B−1B - 1 和 B−5B - 5 都与 AA 同构(都是"一个度 33 的点挂两个叶子、另有一条经度 22 的点延伸一格的枝"), 所以候选是 {1,5}\{1, 5\},取最小值得到答案 11,与样例一致。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:树 AA 与树 BB 各做一次迭代 DFS(O(n)O(n))、一次自底向上的子树统计(O(n)O(n))、 一次自顶向下的换根(O(n)O(n)),这些主体部分构成 O(n)O(n)。 最后把 AA 的 nn 个根哈希装入一个查询结构:Python 版用 set,插入与查询期望 O(1)O(1), 总时间期望 O(n)O(n);C++ 版为了避开 unordered_set 的哈希风险改用排序数组 + binary_search,多一层 O(nlog⁡n)O(n \log n) 的排序,n=105n = 10^5 时实测 0.05 s,同样安全。
  • 空间:邻接表 O(n)O(n),加上父亲的父亲、子树大小、先序序列、子树哈希、根哈希五个长度为 n+2n+2 的数组(C++ 里聚合成一个 Node node[MAXN]),共 O(n)O(n)。
  • 正确性边界:哈希相等是"同构"的必要条件,逆向依赖随机性—— 两棵不同构的树碰巧哈希相等的概率约为 2−642^{-64},n=105n = 10^5 时全部比较的碰撞期望 远小于 10−910^{-9},可以认为不会发生。
  • 与 C++ 解法的关系:main.cpp 是同一算法的 C++ 实现,用一个有序数组加 binary_search 代替 Python 的 set,并用手写迭代 DFS 以避开 10510^5 深链的爆栈问题, 总体复杂度同为 O(nlog⁡n)O(n \log n) / 期望 O(n)O(n) 这一档。
  • 特判:n=1n = 1 时 AA 只有 11 个点、BB 只有一条边, 删掉哪个叶子剩下的都是单点树,直接输出 11(此时 BB 无度大于 11 的点,换根根的选择会失效)。

总结

  • 把形状压成指纹:无法直接比对的"树同构"问题,第一步总是设计一个整树哈希; 一旦有了哈希,"是否存在同构的树"就退化成一次集合查询。
  • 哈希要选可撤销的聚合:本题用的是求和,于是换根与删叶子都只是"减掉一份贡献"这种 O(1)O(1) 操作; 若用最小值、乘积之类不可逆的聚合,就无法做到这一点。
  • 每一项先混淆再聚合:孩子贡献必须先过 mix\mathrm{mix} 再累加, 否则结构化巧合会让不同的孩子集合撞成同一个和;siz\mathrm{siz} 也要混进指纹, 否则不同深度的形状会撞车。
  • 无根树要比"所有根的指纹":只用某一个根的哈希判断同构会漏解, 所以要对 AA 做换根求出 nn 个根哈希全部入集合。
  • 固定根不能取在答案上:BB 的根必须选度数大于 11 的点, 否则当答案恰好是根时,删叶子的公式无父可依。