本文共 1866 字，大约阅读时间需要 6 分钟。

        一棵树，每个节点有一个字符，然后你需要回答m个询问：以v为根的子树，且在原树中深度为h的所有节点上的所有字符，能否组成回文串。

        太弱了，比赛时居然没想到，其实很简单。。直接把询问离线，按照dfs序求解即可。这里有一些技巧，比如，如果一个串是回文，它最多会有1个字符的个数是奇数，其他是偶数。所以我们可以把26个小写字母的奇偶性压成一个int来处理。

        每次dfs到一个节点时，读取与该节点有关的所有询问，把之前得到的那些深度的答案暂存起来（因为不在当前子树），dfs完成一个节点后，用完成时的答案异或开始时的答案，就是这棵子树的答案。离线处理完后统一回答即可。

#include
   
    using namespace std;const int maxn = 5000010;const int maxm = 5000010;char letters[maxn];int head[maxn];int pre[maxn];int to[maxn];int tote;int qhead[maxm];int qpre[maxm];struct Query{    int h;    int others; //保存不在当前子树的统计    int ans;}query[maxm];int totq;bool judge(int x){    if(!x)return 1;    while(!(x&1)){        x>>=1;    }    x>>=1;    return !x;}int h[maxn];void init(){    memset(head,-1,sizeof(head));    tote=0;    memset(qhead,-1,sizeof(qhead));    h[1]=1;}void addedge(int u,int v){    to[tote]=v;    pre[tote]=head[u];    head[u]=tote++;}void addquery(int v,int h,int id){    query[id].h=h;    qpre[id]=qhead[v];    qhead[v]=id++;}int n,m;int cnt[maxn];  //统计每层各字符奇偶void dfs(int u){    //处理与当前节点有关的询问    for(int i=qhead[u];i!=-1;i=qpre[i]){        //存储不在当前子树的统计        query[i].others = cnt[query[i].h];    }    cnt[h[u]]^=(1<<(letters[u]-'a'));    //dfs序遍历    for(int i=head[u];i!=-1;i=pre[i]){        int v = to[i];        h[v]=h[u]+1;        dfs(v);    }    for(int i=qhead[u];i!=-1;i=qpre[i]){        //得到答案        int tmp = query[i].others ^ cnt[query[i].h];        if(judge(tmp)){            query[i].ans=1;        }    }}int main(){    init();    cin>>n>>m;    for(int i=2;i<=n;i++){        int p;        scanf("%d",&p);        addedge(p,i);    }    scanf("%s",letters+1);    for(int i=1;i<=m;i++){        int v,h;        scanf("%d%d",&v,&h);        addquery(v,h,i);    }    dfs(1);    for(int i=1;i<=m;i++){        if(query[i].ans){            printf("Yes");        }else{            printf("No");        }        printf("\n");    }    return 0;}
   

转载地址：https://blog.csdn.net/squee_spoon/article/details/47666667 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！