#P4598. [Sdoi2016]模式字符串
[Sdoi2016]模式字符串
[SDOI2016] 模式字符串
题目描述
给定一棵 个节点的树,每个节点标有一个大写英文字母。再给定一个由大写英文字母组成、长度为 的模式串 。
对有序点对 ,沿从 到 的唯一路径依次读出字母,包含两个端点。当 时只读该节点的一个字母。求有多少有序点对读出的字符串由一个或多个完整的 依次拼接而成。 与 在 时分别计数。
例如,若 为 “PLUS”,则 “PLUSPLUS” 满足要求。若 为 “XYXY”,则 “XYXYXY” 不满足要求。
输入格式
第一行一个整数 ,表示测试组数。每组测试依次给出:
- 两个整数 ,分别是节点数和模式串长度。节点编号为 到 。
- 一个长度为 的大写字母串,第 个字母是节点 的标记。
- 行,每行两个整数 ,表示一条无向边。
- 一个长度为 的大写字母串 。
输出格式
输出 行,每组输出满足条件的有序点对数。
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
数据范围
。每组数据满足 、。
原赛第一子任务占 分,另有 的限制。第二子任务占 分,无额外限制。