BZOJ 3926 [Zjoi2015] 诸神眷顾的幻想乡

发布于 2018-01-05  94 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3926

题意:给一棵叶子节点不超过 20 个的树,求树上有多少种本质不同的子串。


发现一个事实:一条树上路径一定在以某个叶子节点为根的时候是深度单调递增的。

所以考虑以所有叶子节点为根建 trie 树,这样有了一棵大 trie 树,对 trie 树询问本质不同子串的个数。

即广义后缀自动机,流程看代码,为什么看论文吧...

 


一个非常弱的准退役OIER