P17742 题解

TachibanaSherry · 2026-10-22 21:20:09 · 题解

没什么意思的线性做法。

如果加一个超级根连向树的根，每条边的字符是深度较大的点的字符，这样就形成了一个存在重边的字典树，可以用一个 dfs 简单去掉重边，对着这个字典树建立广义 SAM，于是一个询问 x,l 就相当于找到 x 在 parent 树上最浅的祖先 p 满足 len_p\ge l，答案即为节点 p 的 endpos 集合大小，可以在开始时给树上每个节点对应的字典树上节点的 endpos 集合大小加一，然后在 parent 树上做一个子树和即可。

现在问题在怎么对于一个 x,l 找到 p，先对于所有 len,l 分别排个序，然后考虑双指针，对于一个 l，把所有 len_x\ge l 的 x 加入并查集，维护连通块深度最浅的点是什么即可。

建广义 SAM 用哈希表存储转移边，排序用桶排，用个线性并查集科技整道题就是线性的了。