模式字符串
题目描述
给出n个结点的树结构T，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母A到Z,再给出长度为m
的模式串s，其中每一位仍然是A到z的大写字母。Alice希望知道，有多少对结点满足T上从u到V的最短路径
形成的字符串可以由模式串S重复若干次得到？这里结点对是有序的，也就是说和需要被区分.
所谓模式串的重复，是将若干个模式串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的路径形成的字符串恰好是模
式串的若干次重复.
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
数据范围与约定
数据文件太过巨大，仅提供前三组数据测试.