传送门

使用数组表示当前子树内,深度字母为的有多少个

那么可以开始,这样与有关的所有询问都可以快速得出解

差不多就是板子了

储存询问用或链式前向星

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+19;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],ccnt=1;
struct asking{
    int to,nxt; bool ans;
}ask[maxn]; int qhead[maxn],num=1;
void add(int u,int v)
{
    d[++ccnt] = (edge){v,head[u]},head[u]=ccnt;
}
void addask(int u,int h)
{
    ask[++num] = asking{h,qhead[u]},qhead[u] = num;
}
int siz[maxn],son[maxn],n,m;
int cnt[maxn][30],deep[maxn];
char s[maxn];
bool isok(int dep)
{
    int ji=0;
    for(int i=0;i<=25;i++)
        if( cnt[dep][i]%2==1 )    ji++;
    if( ji>1 )    return false;
    return true;
}
void dfs(int u,int fa)
{
    siz[u] = 1; deep[u] = deep[fa]+1;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v== fa )    continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if( siz[v]>siz[son[u]] )    son[u]=v;
    }
}
int SON;
void take(int u,int fa,int val)
{
    cnt[ deep[u] ][s[u]-'a']+=val;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==fa||v==SON )    continue;
        take(v,u,val);
    }
}
void dsu(int u,int fa,int clea)
{
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v = d[i].to;
        if( v==son[u]||v==fa )    continue;
        dsu(v,u,0);
    }
    if( son[u] )    dsu(son[u],u,1),SON = son[u];//保存
    take(u,fa,1); SON = 0;
    for(int i=qhead[u];i;i=ask[i].nxt )
    {
        int dep = ask[i].to;//深度 
        ask[i].ans = isok(dep);
    }
    if( !clea )    take(u,fa,-1);
}
int main()
{
    cin >> n >> m;
    for(int i=2;i<=n;i++)
    {
        int x; scanf("%d",&x);
        add(x,i);
    }
    scanf("%s",s+1);
    for(int i=1;i<=m;i++)
    {
        int v,h; scanf("%d%d",&v,&h);
        addask(v,h);
    }
    dfs(1,0);
    dsu(1,0,0);
    for(int i=2;i<=num;i++)
        printf(ask[i].ans?"Yes\n":"No\n");
}