给出 n 个结点的树 T,其中每一个结点上有一个字符,这里我们所说的字符只考虑大写字母 A 到 Z,再给出长度为 m 的模式串 S,其中每一位仍然是 A 到 Z 的大写字母。
Alice 希望知道,有多少对结点 (u,v) 满足 T 上从 u 到 v 的最短路径形成的字符串可以由模式串 S 重复若干次得到l。
这里结点对 (u,v) 是有序的,也就是说 (u,v) 和 (v,u) 需要被区分。
所谓模式串的重复,是将若干个模式串 s 依次相接(不能重叠)。例如当 S= PLUS的时候,重复两次会得到 PLUSPLUS,重复三次会得到 PLUSPLUSPLUS,同时要注意,重复必须是整数次的。例如当 S= XYXY 时,因为必须重复整数次,所以 XYXYXY 不能看作是 S 重复若干次得到的。