温馨提示:SDOI 2016 二轮省选现场不开栈。
给出 n 个结点的树结构 T,其中每一个结点上有一个字符,这里我们所说的字符只考虑大写字母 A 到 Z ,再给出长度为 m 的模式串 S,其中每一位仍然是 A 到 Z 的大写字母。
Alice 希望知道,有多少对结点 ⟨u,v⟩ 满足 T 上从 u 到 v 的最短路径形成的字符串可以由模式串 S 重复若干次得到?这里结点对 ⟨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
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
子任务
- Subtask 1(20 points): n≤3000
- Subtask 2(80 points): 没有额外的限制
对于所有的数据,1≤C≤10, 1≤n≤100000,1≤m≤20。