hdu 5081 Trie
首先先把题意读明白。
建立出对应Trie的AC自动机，发现题目给出的两个操作都可以对应在Fail树上。
Fail树即把每个节点的fail指针反向构成的树。
我们先研究一下仅修改/查询一个点的情况。
- 修改一个点，即将这个点在Fail树中的子树节点点权全部+1
- 查询一个点，即查询Fail树从根到该节点经过节点的权值和
显然修改/查询多个点就是把修改/查询单个点构成的集合并起来。
将Fail树树链剖分，同时得到了树的dfs序列，子树对应一个区间，根到点的路径对应多条重链的并。
修改很简单，只需求出需要修改的区间的并，再对并修改。
查询的话则需要稍微思考一下，询问的是多条从根到各个节点的并的节点权值和。可以发现其实对于每条重链，被询问的部分对应的都是一个前缀，不可能出现一条重链中间被询问而两边没有的情况。
故只需要对每条重链打个标记表示它被询问到什么位置，如果对于某条重链还要再询问已经完全被询问过的部分，就可以直接break。这样就能保证复杂度。
(鞍山赛区好题真不少，可惜)
Written with StackEdit.