「k-子树匹配」题解

题意简化

给定一棵有根树，定义点 $u$ 的 k-子树 为：$u$ 的子树中所有与 $u$ 距离 $\le k$ 的点构成的树（保留原树结构）。

要求找到最大的 $k$，使得存在两个不同的点 $u \neq v$，它们的 $k$-子树同构（考虑儿子顺序）。

核心思路

1. 问题转化

我们要找两个不同节点的 $k$-子树同构。$k$ 越大，子树越深，匹配难度越大。所以 $k$ 满足单调性：

• 如果 $k$ 可行，那么更小的 $k$ 一定也可行（$k$-子树是 $(k+1)$-子树的子集）
• 因此可以二分答案 $k$

2. 二分框架

二分 $k$，检查是否存在两个不同的节点 $u, v$，使得它们的 $k$-子树同构。

3. 如何判断 $k$-子树同构？

对于每个节点 $u$，我们可以将其 $k$-子树编码成一个哈希值或字符串，用于快速比较同构。

编码方法：

• 从叶子向根处理（自底向上）
• 对于节点 $u$ 的 $k$-子树，考虑它的儿子 $v_1, v_2, \dots, v_m$（按输入顺序）
• 每个儿子 $v$ 的 $(k-1)$-子树已经计算好编码
• 节点 $u$ 的 $k$-子树编码 = 排序或按顺序拼接儿子们的 $(k-1)$-子树编码（加上分隔符）

这样，两个 $k$-子树同构 ⇔ 它们的编码相同。

4. 实现细节

• 哈希：使用字符串哈希或多项式哈希，避免冲突
• 深度限制：只考虑距离 $u$ 不超过 $k$ 的节点
• 记忆化：存储每个节点在不同 $k$ 值下的编码
• 快速查找：用哈希表判断是否存在重复编码

5. 时间复杂度

• 二分：$O(\log n)$ 次
• 每次检查：$O(n)$ 处理所有节点的 $k$-子树编码
• 总复杂度：$O(n \log n)$，可过 $n=10^5$

关键点

1. 单调性 → 二分答案
2. 树哈希 → 快速判断子树同构
3. 自底向上 → 利用 $(k-1)$-子树计算 $k$-子树
4. 儿子顺序 → 编码时要保持原顺序

答案：二分找到的最大 $k$ 即最终解。