题解：P11471 时空轮回

Falashiro · 2024-12-24 00:08:51 · 题解

若要求风景序列 A 在风景序列 B 中的出现次数，则可以每次找到 B 中出现的第一个 A 并在它之后分割，正确性显然。

对于一个序列长度 l，考虑以 \Theta(n) 的时间复杂度求出所有 m_i=l 的询问的答案。

将询问离线，对于所有 m_i=l 的询问，对询问的序列做哈希，并将其哈希值存入哈希表中。我们 dfs 原树，在 dfs 过程中设 f_i 表示第 i 次的询问的序列在 1 号点到当前节点的路径上的出现次数，g_i 表示上一次 f_i 变化的节点。对于一个节点，可以求出以它为末尾的长度为 l 的序列的哈希值，若与第 i 次询问的序列的哈希值相同，则可以根据 g_i 与当前节点的深度差判断是否可以更新 f_i，若 f_i 更新，则同时更新 g_i 与询问答案。dfs 回溯时，需同时回溯 f 与 g。于是我们得到了一个时间复杂度为 \Theta(n) 的处理相同长度的询问的算法。

令 M=\sum m，注意到不同的询问长度至多为 \sqrt M 级别，于是对于每个出现的长度执行以上算法即可。时间复杂度为 \Theta(n\sqrt M)，空间复杂度为 \Theta(n)。