题目地址： 比赛的时候实在没想到DFS序，。。想到DFS序后，分别存起每个深度的所有节点的DFS序，处理出前缀异或和，然后二分找到两个端点，再异或一下，就求出了所求区间的异或和，由于偶数次的都被异或掉了，，所以判断下奇数次数是否大于1即可。 代码如下：
;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;}
只有这样才不会被“不可能”束缚，才能不断超越自我。
