luogu CF570D Tree Requests |dsu on tree

给定一个以1为根的n个节点的树，每个点上有一个字母(a-z)，每个点的深度定义为该节点到1号节点路径上的点数.每次询问 a,ba,ba,b 查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.

---

刚刚学会的dsu on tree

#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN=1e5+10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
const int N=5e5+10;
char s[N]; bool vis[N];
struct node{int id,k;};
vector<node>query[N];
vector<int>G[N];
int n,q,siz[N],son[N],dep[N],cnt[N][26],ans[N];
inline void dfs(int x,int fa){
	siz[x]=1; dep[x]=dep[fa]+1;
	for(int i=0;i<G[x].size();i++){
		int v=G[x][i];
		dfs(v,x);
		siz[x]+=siz[v];
		if(!son[x]||siz[v]>siz[son[x]])son[x]=v;
	}
}
inline void calc(int x,int val){
	cnt[dep[x]][s[x]-'a']+=val;
	for(int i=0;i<G[x].size();i++){
		int v=G[x][i];
		if(vis[v])continue;
		calc(v,val);
	}
}
inline bool check(int sum[]){
	int ret=0;
	for(int i=0;i<26;i++){
		if(sum[i]&1)++ret;
		if(ret>1)return 0;
	}
	if(ret>1)return 0;
	else return 1;
}
inline void dfs2(int x,int keep){
	for(int i=0;i<G[x].size();i++){//遍历轻边
		int v=G[x][i];
		if(v==son[x])continue;
		dfs2(v,0);
	}
	if(son[x])dfs2(son[x],1),vis[son[x]]=1;//遍历重边,标记重儿子
	calc(x,1); vis[son[x]]=0;
	for(int i=0;i<query[x].size();i++)ans[query[x][i].id]=check(cnt[query[x][i].k]);
	if(!keep)calc(x,-1);
}
signed main(){
	cin>>n>>q;
	for(int i=1,f;i<n;i++){
		scanf("%d",&f);
		G[f].push_back(i+1);
	}
	scanf("%s",s+1); dfs(1,0);
	for(int i=1,a,b;i<=q;i++){
		scanf("%d%d",&a,&b);
		query[a].push_back((node){i,b});
	}
	dfs2(1,0);
	for(int i=1;i<=q;i++)puts((ans[i])?"Yes":"No");
	return 0;
}