RT
官方题解自行参考年鉴，很蛋疼，而且跑得也比较慢。今天跟JZP大神讨论了数个小时，YY出了一种新的做法。时间复杂度似乎是O((N+M)*sqrt(N))（JZP和我都没想到怎么严格证这个复杂度，但YY一下感觉是），比官方题解少一个log，而且常数小，实际速度非常给力……
我们考虑两种不同的朴素做法。
一个长度S的字符串在某个长母串里出现了多少次，这个问题可以通过对母串建后缀自动机后直接走一遍，在O(S)时间内回答。于是暴力枚举根节点，DFS整棵树，可以做到O(N^2) N为要计算的树的结点数目。
另一种方法：我们考虑所有过根结点的字符串。这必然可以表示为两条从根节点走下去的路径（要求lca必须是根）。于是对母串正序反序建两颗后缀树，然后就可以O(M)统计。时间复杂度O(M)每个根结点。 M为母串长。
我们对这颗树进行点分治。找重心作为根结点。如果树结点数比较多，就用第二种方法O(M)算出过根结点的答案，然后分治每个子树。否则直接第一种方法O(N^2)算出整棵树的答案，不用继续分治了。
因为点分治产生的“虚拟树”深度是O(lgN)的，而且孩子数越多，对上面的算法越有利。所以最坏情况似乎是原树是二叉树的情况。这时发现假如把“树结点数较多”的标准设为K个，那么第二种方法似乎最多执行O(K)次，每次O(M)；第一种方法似乎最多执行O(N/K)次，每次O(K^2)。
取K=sqrt(N). 发现这时候复杂度O((N+M)*sqrt(N))。
代码写的超级乱，各种调试信息没删…… 不保证可读性…… 哦不对，是保证不可读性…… >__< http://ideone.com/KP82K