#P18799. [Omi2023] 胡安的历史课
[Omi2023] 胡安的历史课
[Omi2023] 胡安的历史课
题目描述
有一棵包含 个顶点的树,顶点编号为 到 。每个顶点上写有一个小写英文字母。
你需要回答 次询问。每次给定两个顶点 和一个非空字符串 。
按照从 到 的方向依次读取这条简单路径上所有顶点的字母,得到字符串 。请判断 是否是 的子序列。
子序列是指从字符串中删除零个或多个字符后,保持剩余字符的原有顺序所得到的字符串。例如,casero 是 canserbero 的子序列。
注意询问有方向。从 到 与从 到 读取的字符串通常不同。若 ,路径字符串只包含该顶点上的一个字母。
输入格式
第一行包含两个整数 。
第二行包含一个长度为 的小写字母字符串,其中第 个字符是顶点 上的字母。
接下来 行,每行包含两个整数 ,表示树的一条无向边。保证输入构成一棵树。
接下来 行,每行包含两个整数 和一个非空小写字母字符串 ,表示一次询问。
输出格式
输出 行。若对应询问中的 是从 到 的路径字符串的子序列,输出 SI;否则输出 NO。
样例输入
10 3
canserbero
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10 casero
2 9 ser
9 3 amar
样例输出
SI
SI
NO
数据范围与分组
设所有询问字符串的长度之和为 。
- ;
- ;
- 。
| 分值 | 额外限制 |
|---|---|
| 10 | ;树的边为 ;所有询问满足 ,且字符串长度为 |
| 20 | |
| ;所有询问的 均相同 | |
| ;树的边为 | |
| 30 | 无额外限制 |