QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 4108. 模式字符串

统计

温馨提示:SDOI 2016 二轮省选现场不开栈。

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

Alice 希望知道,有多少对结点 u,v 满足 T 上从 uv 的最短路径形成的字符串可以由模式串 S 重复若干次得到?这里结点对 u,v是有序的,也就是说 u,vv,u 需要被区分。所谓模式串的重复,是将若干个模式串 S 依次相接(不能重叠)。例如当 S=PLUS 的时候,重复两次会得到 PLUSPLUS,重复三次会得到 PLUSPLUSPLUS。同时要注意,重复必须是整数次的。例如当 S=XYXY 时,因为必须重复整数次,所以 XYXYXY 不能看作是 S 重复若干次得到的。

输入格式

每一个数据有多组测试,

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

对于每一组测试来说:

  • 第一行输入两个整数,分别表示树 T 的结点个数 n 与模式长度 m。结点被依次编号为 1n
  • 之后一行,依次给出了 n 个大写字母(以一个长度为 n 的字符串的形式给出),依次对应树上每一个结点上的字符(第 i 个字符对应了第 i 个结点)。
  • 之后 n1 行,每行有两个整数 uv 表示树上的一条无向边,之后一行给定一个长度为 m 的由大写字母组成的字符串,为模式串 S

输出格式

给出 C 行,对应 C 组测试。每一行输出一个整数,表示有多少对节点 u,v 满足从 uv 的路径形成的字符串恰好是模式串的若干次重复。

样例数据

样例输入

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): n3000
  • Subtask 2(80 points): 没有额外的限制

对于所有的数据,1C10 1n1000001m20