#P18799. [Omi2023] 胡安的历史课

[Omi2023] 胡安的历史课

[Omi2023] 胡安的历史课

题目描述

有一棵包含 NN 个顶点的树,顶点编号为 11 到 NN。每个顶点上写有一个小写英文字母。

你需要回答 QQ 次询问。每次给定两个顶点 u,vu,v 和一个非空字符串 SS。

按照从 uu 到 vv 的方向依次读取这条简单路径上所有顶点的字母,得到字符串 PP。请判断 SS 是否是 PP 的子序列。

子序列是指从字符串中删除零个或多个字符后,保持剩余字符的原有顺序所得到的字符串。例如,casero 是 canserbero 的子序列。

注意询问有方向。从 uu 到 vv 与从 vv 到 uu 读取的字符串通常不同。若 u=vu=v,路径字符串只包含该顶点上的一个字母。

输入格式

第一行包含两个整数 N,QN,Q。

第二行包含一个长度为 NN 的小写字母字符串,其中第 ii 个字符是顶点 ii 上的字母。

接下来 N−1N-1 行,每行包含两个整数 u,vu,v,表示树的一条无向边。保证输入构成一棵树。

接下来 QQ 行,每行包含两个整数 u,vu,v 和一个非空小写字母字符串 SS,表示一次询问。

输出格式

输出 QQ 行。若对应询问中的 SS 是从 uu 到 vv 的路径字符串的子序列,输出 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

数据范围与分组

设所有询问字符串的长度之和为 LL。

  • 2≤N,Q≤3000002\le N,Q\le300000;
  • 1≤u,v≤N1\le u,v\le N;
  • Q≤L≤300000+QQ\le L\le300000+Q。
分值 额外限制
10 N,Q≤105N,Q\le10^5;树的边为 (i,i+1)(i,i+1);所有询问满足 u=1u=1,且字符串长度为 11
20 N,Q≤1000,L≤2000N,Q\le1000,L\le2000
N,Q≤105,L≤200000N,Q\le10^5,L\le200000;所有询问的 u,vu,v 均相同
N,Q≤105,L≤200000N,Q\le10^5,L\le200000;树的边为 (i,i+1)(i,i+1)
30 无额外限制