模式字符串
测试数据来自 system/1995
描述
给出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重复若干次得到的。
格式
输入格式
第一行输入两个整数,分别表示树T的结点个数n与模式长度m。结点被依次编号为1到n。之后一行,依次给出了n个大写字母(以一个长度为n的字符串的形式给出),依次对应树上每一个结点上的字符(第i个字符对应了第i个结点)。之后n-1行,每行有两个整数u和v表示树上的一条无向边。之后一行,给定一个长度为m的由大写字母组成的字符串,为模式串S。
输出格式
输出一个整数,表示有多少对叶子节点<u,v>满足从u到v的路径形成的字符串恰好是模式串的若干次重复。
样例1
样例输入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
样例输出1
5
限制
对于20%的数据,3<=n<=3000且3<=m<=3000。
对于100%的数据,3<=n<=1000000且3<=m<=1000000。
此外还存在40%的数据,满足3<=n<=100000且3<=m<=30。
来源
SDOI 2016 round2 day1
信息
- ID
- 1927
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者