Codeforces Round #316 (Div. 2) D. Tree Requests (DFS序)

题目地址：http://codeforces.com/contest/570/problem/D
比赛的时候实在没想到DFS序，。。想到DFS序后，分别存起每个深度的所有节点的DFS序，处理出前缀异或和，然后二分找到两个端点，再异或一下，就求出了所求区间的异或和，由于偶数次的都被异或掉了，所以判断下奇数次数是否大于1即可。
代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <time.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
#pragma comment(linker, "/STACK:1024000000")
const LL mod=3221225473;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=500000+10;
vector<int>vec[MAXN];
vector<int>::iterator it;
int in[MAXN], out[MAXN], sum[MAXN];
int head[MAXN], cnt, now;
char s[MAXN];
struct node
{
        int u, v, next;
}edge[MAXN];
void add(int u, int v)
{
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void init(int n)
{
        memset(head,-1,sizeof(head));
        cnt=now=0;
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++){
                vec[i].clear();
                vec[i].push_back(0);
        }
}
void dfs(int u, int h)
{
        now++;
        sum[now]=sum[*(--vec[h].end())]^(1<<s[u]-'a');
        vec[h].push_back(now);
        in[u]=now;
        for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].v;
                dfs(v,h+1);
        }
        out[u]=now;
}
int main()
{
        int n, m, i, j, u, h, ans, l, r, flag;
        while(scanf("%d%d",&n,&m)!=EOF){
                init(n);
                for(i=2;i<=n;i++){
                        scanf("%d",&u);
                        add(u,i);
                }
                scanf("%s",s+1);
                dfs(1,1);
                while(m--){
                        scanf("%d%d",&u,&h);
                        it=lower_bound(vec[h].begin(),vec[h].end(),out[u]);
                        if((*it)!=out[u]) it--;
                        r=sum[*it];
                        it=--lower_bound(vec[h].begin(),vec[h].end(),in[u]);
                        l=sum[*it];
                        ans=r^l;
                        flag=0;
                        for(i=0;i<26;i++){
                                if(ans&(1<<i)) flag++;
                                if(flag==2) break;
                        }
                        if(flag==2) puts("No");
                        else puts("Yes");
                }
        }
        return 0;
}