1 条题解
-
0
题目理解
我们有一棵 N 个节点的树，每个节点上有一个小写字母（颜色）。
我们要找一条路径（节点序列），使得 从一端到另一端的颜色序列 与 反过来从另一端到这一端的颜色序列 完全相同，即路径上的颜色序列是回文的。路径长度定义为路径上节点的个数。
样例分析
样例 1
7 imanade 1 2 2 3 3 4 4 5 5 6 6 7树是一条链：1-2-3-4-5-6-7
颜色：i m a n a d e检查所有路径：
- 路径 3-4-5：颜色 a n a 是回文，长度 3。
- 没有更长的回文路径。
输出：3
样例 2
4 aabb 1 2 1 3 3 4树结构：
2 \ 1--3--4颜色：1:a, 2:a, 3:b, 4:b
路径 2-1-3 颜色 a a b 不是回文。
路径 1-3-4 颜色 a b b 不是回文。
路径 2-1 颜色 a a 是回文，长度 2。
路径 3-4 颜色 b b 是回文，长度 2。输出：2
样例 3
8 acdbabcd 1 6 6 7 6 3 3 4 4 5 5 2 8 5树结构（大致）：
7 2 8 \ \ / 6 5 \ / 3 | 4颜色：a c d b a b c d
路径 8-5-2 颜色 d b b 不是回文。
路径 7-6-3-4 颜色 c d b a 不是回文。
路径 1-6-3-4-5 颜色 a c d b a 是回文，长度 5。输出：5
问题难点
- N 最大 50000，不能枚举所有路径（O(N²) 会超时）。
- 路径可以在树中任意弯曲，不一定是直链。
- 回文要求路径上颜色对称，长度可以是奇数或偶数。
思路分析
1. 回文路径的性质
- 如果路径长度为奇数，则有一个中心节点，两边对称。
- 如果路径长度为偶数，则中心在一条边的中间，两边完全对称。
- 路径对称意味着：从中心向两边走，每一步的颜色必须相同。
2. 常见错误思路
直接枚举所有路径中心然后向两边扩展，但树不是线性的，扩展时要考虑树的分支，容易重复或漏算。
3. 正确解法框架
这个问题是 树上最长回文路径，常用方法是：
(1) 点分治（重心分解）
- 在点分治的每一层，考虑经过当前重心的路径。
- 对每个子树，我们记录从重心出发到子树中节点的路径颜色序列（正序和反序）。
- 用哈希表示路径的颜色序列，以便快速比较正序和反序是否相等（回文）。
- 同时要保证路径是简单路径（不重复节点）。
(2) 哈希技巧
- 给每个颜色分配一个随机大整数。
- 路径的正向哈希 = 多项式哈希，反向哈希 = 反向多项式哈希。
- 如果正向哈希 = 反向哈希，则路径是回文。
- 双哈希避免碰撞。
(3) 合并子树信息
- 在点分治时，对于当前重心，我们分别考虑奇数长度和偶数长度回文路径。
- 奇数：中心在节点，偶数：中心在边。
- 用 map 或 unordered_map 存储之前子树中出现的（哈希值，深度）等信息，与当前子树匹配。
4. 时间复杂度
- 点分治 O(N log N)，每层处理 O(N) 或 O(N log N)（如果使用 map）。
- 总体 O(N log² N) 或 O(N log N) 取决于实现。
5. 算法步骤概要
- 读入树和颜色。
- 建立邻接表。
- 实施点分治：
- 找重心。
- 标记已访问。
- 对重心的每个邻居子树：
- DFS 收集所有从重心出发的路径（正向哈希、反向哈希、长度）。
- 与之前子树的路径匹配，看是否能形成回文路径。
- 递归处理子树。
- 输出找到的最大长度。
关键点
- 哈希比较时，要确保路径不重叠（点分治保证经过重心，且来自不同子树）。
- 注意奇数/偶数中心分开处理。
- 随机化哈希基数和模数，防止被卡。
这样，我们就能在 O(N log² N) 时间内求出最长的回文路径长度。
- 1