题意

我们需要按照 DFS 顺序记录顶点，并存储每个顶点在 DFS 中的进入/离开时间。子树中的所有顶点构成一个连续的区间。这样，对于深度为 $h$ 的子树 $v$，我们可以通过两次二分查找得到该子树中所有深度为 $h$ 的顶点所对应的区间。

如果每个字母出现的次数中，出现次数为奇数的字母数量小于 $2$，则可以构成回文串。

思路

对于遍历过程中的每个深度，我们可以统计每个前缀中各个字母出现的次数。

为了节省内存，可以使用位压缩，因为我们只需要记录每个字母出现次数的奇偶性，而奇偶性可以通过异或运算来维护。

算法步骤

1. 对树进行 DFS，记录每个顶点的进入时间（tin）和离开时间（tout），同时记录每个顶点所在的深度。
2. 在 DFS 过程中，对于每个深度，维护一个数组或位掩码，表示从根节点到当前顶点的路径上，每个字母出现次数的奇偶性。
3. 对于每个查询 $(v, h)$：
   • 确定子树 $v$ 中深度为 $h$ 的所有顶点所在的区间（通过二分查找）。
   • 在该区间内，利用前缀奇偶信息，计算所有顶点对应的字母奇偶性的异或和。
   • 检查异或结果中 $1$ 的个数是否小于 $2$，若是则输出 Yes，否则输出 No。

复杂度分析

• 时间复杂度：$O(m \cdot (\log n + 26) + n)$
• 另一种离线解法的时间复杂度为 $O(n + m \cdot (26 / 32))$，空间复杂度为 $O(n \cdot 26 / 8)$

代码说明

• 使用 DFS 遍历树，记录每个顶点的进入时间和离开时间，以及每个深度下的顶点列表。
• 对于每个深度，维护一个前缀异或数组，记录从根到当前顶点路径上每个字母出现次数的奇偶性。
• 对于每个查询，通过二分查找定位子树中指定深度的顶点区间，然后利用前缀异或快速计算该区间内所有顶点的奇偶性异或和，最后判断是否满足回文条件。

#include<bits/stdc++.h>
#define M 500005
using namespace std;
struct query{
	int de,id;
};
int n,m;
vector<int>G[M],tmp[M];
vector<query>Q[M];
int cnt[M],ans[M];
char A[M];
void dfs(int v,int d){
	cnt[d]^=1<<A[v]-'a';
	for(int i=0;i<Q[v].size();i++)
		tmp[v].push_back(cnt[Q[v][i].de]);
	for(int i=0;i<G[v].size();i++)
		dfs(G[v][i],d+1);
	for(int i=0;i<Q[v].size();i++)
		ans[Q[v][i].id]=(tmp[v][i]^cnt[Q[v][i].de]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2,f;i<=n;i++){
		scanf("%d",&f);
		G[f].push_back(i);
	}
	scanf("%s",A+1);
	for(int i=1;i<=m;i++){
		int x,d;
		scanf("%d%d",&x,&d);
		Q[x].push_back((query){
			d,i
		});
	}
	dfs(1,1);
	for(int i=1;i<=m;i++)
		puts(ans[i]==(ans[i]&-ans[i])?"Yes":"No");
	return 0;
}