模式字符串

模式字符串

题目描述

给出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时,因为必须重复整数次,所以X

YXYXY不能看作是S重复若干次得到的。

输入格式

每一个数据有多组测试,

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

对于每一组测试来说:

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

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

第i个字符对应了第i个结点).

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

为模式串S。

1<=C<=10,3<=N<=10000003<=M<=1000000

输出格式

给出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

提示

数据文件太过巨大,仅提供前三组数据测试.

By AHdoc命题 鸣谢CreationAugust上传

信息

难度
10
分类
(无)
标签
递交数
4
已通过
0
通过率
0%
上传者