以下为自己口胡,未经网上搜索题解验证
Statement
一棵 \(n\) 个点的树,每条边有一个小写字母边权,\(m\) 次询问,每次给定 \(u,v,s\),问字符串 \(s\) 在 \(u\to v\) 路径组成的字符串中出现了几次。\(n,m\le 10^5,\sum|s|\le 3\cdot10^5\).
Solution
Sol 1
把 \(u\to v\) 路径拆成 \(u\to lca,lca\to v\) 两条路径,答案等于 \(u\to lca\) 中 \(s\) 的出现次数 \(+\) \(lca\to v\) 中 \(s\) 的出现次数 \(+\) \(s\) 经过 \(lca\) 的出现次数。
“\(s\) 经过 \(lca\) 的出现次数”由于 \(\sum|s|\le 3\cdot10^5\),直接把 \(lca\) 两边长度为 \(|s|\) 的串拼起来,跑 KMP / ACAM 即可。
问题变成分别求“\(u\to lca\) 中 \(s\) 的出现次数”与“\(lca\to v\) 中 \(s\) 的出现次数”。第一问可转化为“\(u\to root\) 中 \(s\) 的出现次数”,第二问可转化为“\(root\to u\) 中 \(s\) 的出现次数”,直接差分一下就是第一二问真正的答案。
“\(u\to root\) 中 \(s\) 的出现次数”又可以转化为“\(root\to u\) 中 \(s\) 的反串的出现次数”,于是问题变成了快速求 \(root\to u\) 中 \(s\) 的出现次数。
把所有询问离线到每个 \(u\) 上,对于所有 \(s\) 建 ACAM,考虑 DFS 一遍求出所有答案。
当 \(u\) 向他的一个儿子 \(v\) 走,那么 \(pos(u)\) 对应的在 ACAM 上走一步 \(w(u,v)\) 得到 \(pos(v)\)。
可以这样解决:每次在 \(pos(u)\) 上单点加,对于询问 \((u,s_i)\) 就查 ACAM 上 \(s_i\) 子树和就行了,树状数组可以维护,回溯时撤回修改。
Sol 2
树剖,每个重链维护 SAM,预处理 SAM 上每个点的 \(\text{endpos}\) 集合大小,对于重链直接按 \(s\) 在 SAM 上走即可,轻重链切换位置需要暴力匹配。\(O(m\log n)\).
不会其他做法了 QAQ
标签:le,出现,ACAM,次数,4231,lca,root,回忆,BZOJ From: https://www.cnblogs.com/laijinyi/p/18403596