题目理解

给定一棵 $n$ 个节点的树，每个节点有一个大写字母。
再给一个长度为 $m$ 的模式串 $S$。
问有多少有序节点对 $\langle u, v \rangle$，使得从 $u$ 到 $v$ 的简单路径上的字母连成的字符串，恰好等于 $S$ 重复 $k$ 次（$k \ge 1$ 整数）。

样例分析

样例：

n=11, m=4
节点上的字母：IODSSDSOIOI
边：
1-2, 2-3, 3-4, 1-5, 5-6, 6-7, 3-8, 8-9, 6-10, 10-11
S = "SDOI"

输出 5。

说明有 5 条路径的字符串是 SDOI 重复整数次（这里主要是 SDOI 一次，因为 m=4，路径长度 4 的倍数才可能）。

思路分析

1. 路径特征

• 路径长度 $L$（边数）必须是 $m$ 的倍数，设 $L = k \cdot m$。
• 路径上第 $i$ 个节点（从起点 $u$ 开始数）的字符必须等于 $S[i \bmod m]$。

2. 统计方法

• 最直接的想法是枚举所有 $O(n^2)$ 路径，不可行。
• 树上的路径统计问题，常用点分治。
• 在点分治框架下，考虑经过重心 $r$ 的路径 $u \to r \to v$，将其拆成 $u \to r$（反向）和 $r \to v$（正向）两段。
• 我们需要合并两段路径，使得总长度 $len_u + len_v = k \cdot m$，并且字符串匹配 $S$ 的重复。

3. 字符串匹配处理

• 为了快速判断路径字符串是否匹配 $S^k$，使用字符串哈希。
• 预处理 $S$ 重复两次的哈希值，方便计算任意 $S^k$ 的哈希。
• 对于 $u \to r$ 的反向路径，需要反转后与 $S$ 匹配，可以预处理 $S$ 的反串的哈希。

4. 点分治中的匹配规则

设：

• $A$ = $u \to r$ 的路径字符串（从 $u$ 到 $r$ 方向），长度为 $a$。
• $B$ = $r \to v$ 的路径字符串（从 $r$ 到 $v$ 方向），长度为 $b$。

那么 $u \to v$ 的字符串是 $A^{reverse} + B$，总长度 $a+b$。

条件：

1. $(a+b) \bmod m = 0$
2. $A^{reverse}$ 必须匹配 $S$ 的某个后缀，$B$ 必须匹配 $S$ 的某个前缀，并且 $A^{reverse} + B$ 正好是 $S$ 的整数倍重复。

更具体：

• 设 $t = a \bmod m$。
• 那么 $A^{reverse}$ 应等于 $S[m-t \ldots m-1]$（即 $S$ 的最后 $t$ 个字符的反向？这里要注意方向），实际上 $A^{reverse}$ 应当匹配 $S$ 的前 $t$ 个字符的反向？需要仔细推导。

实际上更稳妥的方法：

• 对 $u \to r$ 路径，记录哈希时按照从 $r$ 到 $u$ 方向计算哈希（即正向视为 $r \to u$ 的字符串），这样 $u \to r$ 反向就是正序 $r \to u$ 的字符串的反向，但哈希可以反向计算。
• 我们预先计算 $S$ 的正向哈希 $H$ 和反向哈希 $H_{rev}$。
• 在点分治时，对从重心 $r$ 出发到 $x$ 的路径，记录：
  • 长度 $dep$
  • 哈希值 $h$（从 $r$ 到 $x$ 方向）
  • 反向哈希值 $h_{rev}$（从 $x$ 到 $r$ 方向，即路径反向的哈希）

合并时：

• $u \to r$ 段用反向哈希（因为实际方向是 $u \to r$，对应字符串是 $r \to u$ 的反向）
• $r \to v$ 段用正向哈希
• 总哈希 = $h_{rev}(u \to r) \times B^{b} + h(r \to v)$，其中 $b$ 是 $r \to v$ 的长度。
• 检查是否等于 $H(S^{k})$，其中 $k = (a+b)/m$。

5. 优化

• 用哈希表存储从重心出发的路径信息（长度模 $m$，哈希值，方向等），然后匹配对应的“另一半”路径。
• 注意去重，保证 $u$ 和 $v$ 在重心的不同子树。

算法步骤

1. 预处理 $S$ 重复两次的正向哈希和反向哈希，以及 $B^{len}$ 的幂。
2. 点分治：
   • 找重心
   • 对每个子树 DFS，记录路径信息（长度，哈希，反向哈希，子树标号）
   • 用哈希表统计当前已遍历子树的路径
   • 遍历新子树时，先查询已存路径中能匹配的路径数，再加入新子树路径
3. 统计所有经过重心的合法路径数。
4. 递归处理子树。

复杂度

• 点分治 $O(n \log n)$
• 哈希比较 $O(1)$
• 总复杂度 $O(n \log n)$，可过 $10^6$ 数据。