【bzoj4231】回忆树

Source

bzoj4231

Hint

请先思考后再展开

首先肯定把树上路径拆分成两段,中间拉出来用kmp之类的算一算就好了

Solution

请先思考后再展开

方法一:在线,log方
建出trie然后建广义sam(这样复杂度是对的),线段树合并求出每个节点right集合,然后每个询问用树剖划分为log段区间询问
方法二:离线,log方
和上面差不多,把询问串建成ac自动机,然后把树放上去匹配
注意很重要的一点,ac自动机建完后要预处理出每种字母失配后到达哪里(有些板子本来就有可以忽略),否则很好卡
方法三:离线,log
考虑把刚才向上的路径再次拆分成两段到根节点的路径
设当前询问串长度为|S|,向上k,则为pp(x)-pp(fa(x,k-|S|))
那么还是把整棵树放上去ac自动机上跑,然后因为询问是要求来自x到根路径
所以充分利用dfs的特性,子树和(用树状数组维护)只存向上的点产生的影响即可
(最后这点没有想到,卡了很久)

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a9a.html
转载请注明出处,谢谢!