反回文串是指对于某个长度为n的字符串s,对于∀i∈[0,n),均满足s[i]=s[n−1−i]。
例如,字符串codeforces,love是反回文串,但是you,abbc就不是反回文串。
给你一个 n 个节点的有根树,树的根节点为1,树的每个节点上有一个小写字母。
有 q 次询问,每次询问给出两个值now,deep,代表对于节点now,其子树中所有对于根来说深度为deep(根的深度为1)的节点上的字母组成的集合能否构成一个反回文串。
第一行,两个整数 n,q(1≤n≤2⋅105;1≤q≤2⋅105),代表树的节点数与询问数。
接下来的n−1行,每行两个整数 u,v(1≤u,v≤n),代表树上的一条边,保证最终给出的是一棵树。
接下来的一行,一个长度为n的字符串s,其中s[i−1]代表节点i上的字母。
接下来的q行,每行两个整数 now,deep(1≤now,deep≤n) ,代表一次询问。
对于每个询问,如果可以构成反回文串,输出Yes。
如果这次询问中的 deep<dep[now] 或者深度为deep的子节点不存在或无法构成反回文串,输出No。
本题的输出大小写不敏感,即"YES"、"yEs"等均会被视作肯定的答案。
输入样例:
5 3
1 2
1 3
2 4
2 5
aabcc
1 2
3 3
2 3
输出样例:
Yes
No
No
样例解释:
对于询问 1 2,当前可以构成反回文串ab。
对于询问 3 3,深度为3的子节点不存在。
对于询问 2 3,cc显然不是反回文串。