codeforces 570 D. Tree Requests (dfs序)

因为字母的排列顺序是任意的,所以判断能否形成回文串的条件就成了出现次数为奇数的字母的个数是否大于1个,如果是,那么一定不能形成回文串,否则一定可以.

为了找到以节点v为根的 subtree 中深度为h的后代,需要求出dfs序列,并且记录每个节点初次访问的时间戳和离开它的时间戳,然后二分.

貌似也可以用树状数组做?

1/*************************************************************************
2	> File Name: code/cf/#316/D.cpp
3	> Author: 111qqz
4	> Email: rkz2013@126.com 
5	> Created Time: 2015年08月15日 星期六 02时55分55秒
6 ************************************************************************/
7#include <bits/stdc++.h>
1using namespace std;
2const int N=5E5+7;
3int n,m;
4vector<int> adj[N];
5char S[N];
6vector<int> occ[N][26];
7int in[N], out[N], now;
 1void dfs(int u, int depth)
 2{
 3    occ[depth][S[u]-'a'].push_back(++now);
 4    in[u]=now;
 5    vector<int>::iterator it;
 6    for (it=adj[u].begin();it!=adj[u].end();it++)
 7    {
 8	dfs(*it,depth+1);
 9    }
10    out[u]=now;
11}
 1int main()
 2{
 3    scanf("%d %d",&n,&m);
 4    for(int i=2; i<=n; i++)
 5    {
 6        int a;
 7        scanf("%d",&a);
 8        adj[a].push_back(i);
 9    }
10    scanf("%s", S+1);
11    dfs(1, 1);
12    while(m--)
13    {
14        int v, h;
15        scanf("%d %d",&v,&h);
16        int odd=0;
17        for(int i=0; i<26; i++)
18        {
19            int cnt=upper_bound(occ[h][i].begin(), occ[h][i].end(), out[v])-
20                    lower_bound(occ[h][i].begin(), occ[h][i].end(), in[v]);
21            if(cnt%2==1)
22            {
23                odd++;
24                if(odd>1)
25                    break;
26            }
27        }
28        if(odd>1)
29            printf("No\n");
30        else
31            printf("Yes\n");
32    }
33    return 0;
34}