No Abstract.

Des.

给出$n$个结点的树结构$T$，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母$A$到$Z$，再给出长度为$m$的模式串$s$，其中每一位仍然是A到z的大写字母。

Alice希望知道，有多少对结点满足T上从u到v的最短路径形成的字符串可以由模式串S重复若干次得到？

这里结点对是有序的，也就是说和需要被区分。

所谓模式串的重复，是将若干个模式串S依次相接（不能重叠)。例如当$S$=PLUS的时候，重复两次会得到PLUSPLUS，重复三次会得到PLUSPLUSPLUS，同时要注意，重复必须是整数次的。例如当$S$=XYXY时，因为必须重复整数次，所以XYXYXY不能看作是$S$重复若干次得到的。

Sol.

记得树上点对计数时想想点分治.

统计以$x$为根的子树, 起点为$x$的链时, 若当前链是模式串复制的前/后$k$位, 就丢到模$m$意义的桶里去, 同时把他以前的兄弟, 和他互补的桶之和加到答案里.

退出后把桶也丢进桶之和中. 然后继续分治下去即可.

1
2