DSU on tree确实很厉害，然后这变成了一道裸题(逃
还是稍微说一下流程吧，虽然我那个模板汇总里写过
DSU on tree可以以$O(n\log n)$的复杂度解决树上子树统计问题，它这样工作：
前置工作：对树进行轻重链剖分
1.递归求解所有的轻儿子，在回溯时消去影响
2.递归进入重儿子，在回溯时不消去影响
3.暴力统计子树信息
4.回答询问并回溯
根据轻重链剖分的性质，复杂度$O(n\log n)$
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
vector<pair<int,int> > qry[N];
int siz[N],dep[N],imp[N],sta[N],vis[N],outp[N];
int p[N],noww[*N],goal[*N];
int n,m,t1,t2,rd,cnt;
char str[N];
void Link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
noww[++cnt]=p[t];
goal[cnt]=f,p[t]=cnt;
}
int Bitcount(int s)
{
int ret=;
while(s)
ret++,s-=s&-s;
return ret;
}
void DFS(int nde,int fth,int dth)
{
int tmp=;
siz[nde]=,dep[nde]=dth;
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
{
DFS(goal[i],nde,dth+);
siz[nde]+=siz[goal[i]];
if(siz[goal[i]]>tmp)
tmp=siz[goal[i]],imp[nde]=goal[i];
}
}
void Count(int nde,int fth)
{
sta[dep[nde]]^=<<(str[nde]-'a');
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&!vis[goal[i]])
Count(goal[i],nde);
}
void Getans(int nde,int fth,int hvy)
{
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&goal[i]!=imp[nde])
Getans(goal[i],nde,);
if(imp[nde])
Getans(imp[nde],nde,),vis[imp[nde]]=true;
Count(nde,fth);
vector<pair<int,int> >::iterator it;
for(it=qry[nde].begin();it!=qry[nde].end();it++)
{
int dth=it->second;
outp[it->first]=(Bitcount(sta[dth])<=);
}
if(imp[nde]) vis[imp[nde]]=false;
if(!hvy) Count(nde,fth);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%d",&t1),Link(t1,i+);
scanf("%s",str+);
for(int i=;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
qry[t1].push_back(make_pair(i,t2));
}
DFS(,,),Getans(,,);
for(int i=;i<=m;i++)
outp[i]?puts("Yes"):puts("No");
return ;
}