9674 - 模式字符串

给出 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 重复若干次得到的。

每一个数据有多组测试，

第一行输入一个整数 C，表示总的测试个数。

对于每一组测试来说：

第一行输入两个整数，分别表示树 T 的结点个数 n 与模式长度 m。结点被依次编号为 1 到 n。

之后一行，依次给出了 n 个大写字母（以一个长度为n的字符串的形式给出），依次对应树上每一个结点上的字符（第 i 个字符对应了第 i 个结点)。

之后 n-1 行，每行有两个整数 u 和 v 表示树上的一条无向边，之后一行给定一个长度为 m 的由大写字母组成的字符串，为模式串 S。

给出 C 行，对应 C 组测试。

每一行输出一个整数，表示有多少对节点 (u,v) 满足从 u 到 v 的路径形成的字符串恰好是模式串的若干次重复。

1\leq C\leq 10，3\leq \sum N\leq 10^6，3\leq \sum M\leq 10^6。

山东省选