1.思路

对于这题来说,总的来说还是dsu的一个板子,我们计算完了之后暴力更新就好了.复杂度是O(26*nlogn)的.

2.代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50,M=26;
struct DSU{
    int id,k;
};
vector<DSU>ask[N];
vector<int>v[N];
bool ans[N];//存询问的答案.
char s[N];
int dep[N],sz[N],dfn[N],Son;
int tot[M][N];//统计当前在深度为u时的s[i]个数.

void cal(int u,int fa,bool op)
{
    if(op)    tot[s[u]-'a'][dep[u]]++;
    else    tot[s[u]-'a'][dep[u]]--;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa||son==Son)    continue;
        cal(son,u,op);
    }
}
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;sz[u]=1;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa)    continue;
        dfs(son,u);
        sz[u]+=sz[son];
        if(sz[son]>sz[dfn[u]])    dfn[u]=son;
    }
}

void dfs(int u,int fa,bool op)
{
    //printf("%d\n",u);
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa||son==dfn[u])    continue;
        dfs(son,u,true);
    }
    if(dfn[u])    dfs(dfn[u],u,false),Son=dfn[u];
    cal(u,fa,true);
    for(int i=0;i<(int)ask[u].size();i++)
    {
        int id=ask[u][i].id;
        int Dep=ask[u][i].k;
        //printf("%d %d %dssss\n",id,u,Dep);
        int cnt=0;
        for(int j=0;j<26;j++)
        {
            if(tot[j][Dep]&1)    cnt++;
        }
        //printf("%d %daaaa\n",id,cnt);
        if(cnt<2) ans[id]=1;
    }
    Son=0;
    if(op)
    {
        cal(u,fa,false);
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
    {
        int x;scanf("%d",&x);
        v[i].push_back(x);
        v[x].push_back(i);
    }dfs(1,0);scanf("%s",s+1);
    for(int i=1;i<=m;i++)
    {
        int u,x;
        scanf("%d%d",&u,&x);
        ask[u].push_back({i,x});
    }dfs(1,0,0);
    for(int i=1;i<=m;i++)
        ans[i]==1?puts("Yes"):puts("No");
    return 0;
}
/*
为什么题目写少了,连基本的验证答案都不会了.
*/