自动搬运

查看原文

来自洛谷，原作者为

	Falashiro 丝之歌什么时候出

搬运于2025-08-24 23:07:39，当前版本为作者最后更新于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)$。