#2065. 「SDOI2016」模式字符串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

Alice 希望知道,有多少对结点 \langle u, v \rangle 满足 T 上从 u v 的最短路径形成的字符串可以由模式串 S 重复若干次得到?这里结点对 \langle u,v \rangle 是有序的,也就是说 \langle u, v \rangle \langle v, u \rangle 需要被区分。所谓模式串的重复,是将若干个模式串 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 组测试。每一行输出一个整数,表示有多少对节点 \langle u,v \rangle 满足从 u v 的路径形成的字符串恰好是模式串的若干次重复。

样例

样例输入

1
11 4
IODSSDSOIOI
1 2
2 3
3 4
1 5
5 6
6 7
3 8
8 9
6 10
10 11
SDOI

样例输出

5

数据范围与提示

对于所有的数据, 1 \leq C \leq 10, \ 3 \leq \sum n \leq 1000000, 3 \leq \sum M \leq 1000000