Tree Requests

题意

给你一棵有 个节点以 为根的树，每个节点为 的任意字母。有 次询问，每次询问给出 ，指以 为根的子树内深度为 的所有节点的字母在排列后能否构成一个回文串。

分析

要排列后成为回文串，所以在符合条件的所有节点之中至多只有一种字母的数量为奇数个，其余的字母数量必定均为偶数个。
因为回文串的总长如果为偶数，那么所有的字母必定成对（即偶数个）出现；如果长度为奇数，那么只会有一个字母有奇数个，其余均为偶数。

之后就是基本的 的操作了，先将所有的询问以离线的方式存储下来，这样我们就可以一边，一边解决所有的询问，之后统计所有深度,字母的出现次数以便我们的 ，再将轻边子树的信息保留到重链之上进行一个答案的统计。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m,cnt;
int head[N],siz[N],sum[N],son[N],dep[N],ans[N],tot[N][26];
bool vis[N];
char s[N];
struct node
{
    int to,nxt;
}e[N<<1];
struct rec
{
    int k,id;
};
std::vector<rec> q[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    siz[x]=1;dep[x]=dep[fa]+1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)    continue ;
        dfs(v,x);siz[x]+=siz[v];
        if(!son[x]||siz[v]>siz[son[x]])    son[x]=v;
    }
}

void calc(int x,int fa,int val)
{
    tot[dep[x]][s[x]-'a']+=val;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa||vis[v])    continue ;
        calc(v,x,val);
    }
}

bool check(int s[])
{
    int r=0;
    for(int i=0;i<26;i++)
    {
        if(s[i]&1) ++r;
        if(r>1)    return 0;
    }
    if(r>1)    return 0;
    return 1;
}

void dfs2(int x,int fa,int keep)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa||v==son[x])    continue;
        dfs2(v,x,0);
    }
    if(son[x])    dfs2(son[x],x,1),vis[son[x]]=1;
    calc(x,fa,1),vis[son[x]]=0;
    for(int i=0;i<q[x].size();i++)    ans[q[x][i].id]=check(tot[q[x][i].k]);
    if(!keep)    calc(x,fa,-1);
}

int main()
{
    n=read();m=read();
    for(int i=2;i<=n;i++)
    {
        int u=read();
        add(u,i);add(i,u);
    }
    scanf("%s",s+1);
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int a=read(),b=read();
        q[a].push_back((rec){b,i});
    }
    dfs2(1,0,0);
    for(int i=1;i<=m;i++)
     if(ans[i])    printf("Yes\n");
     else printf("No\n");
    return 0;
}