CF570D Tree Requests

题意：
给定一个以1为根的n个节点的树，每个点上有一个字母(a-z)，每个点的深度定义为该节点到1号节点路径上的点数.每次询问 a,b 查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.
题解：
dfs序+状态压缩+二分查找
这个题用到了很多小技巧，比如说异或前缀和等等。
我们首先对他跑一边dfs序，记录下每个点的时间戳。
把每个层点入度的时间戳放在一起，因为结点到某层，也要保证这一层是他的孩子。
所以我们用这个时间戳来确定到底是这一层的哪一段。
用二分查找分别找入度结点和出度结点，从而确定范围。
字母一共只有26个，于是考虑状态压缩。再对每层开一个vector维护前缀状态。
再用异或前缀和的小方法，在O(1)的时间复杂度内确定字母的奇偶的个数。
如果奇数个数大于1，那么则输出No

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long

#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =5e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

int n,m;
string s;
vector<int> edge[maxn];
int in[maxn],out[maxn];
int deep[maxn];
vector<int>arr[maxn],inn[maxn],b[maxn];

int cnt,maxdeep;
void dfs(int u,int fa){
    in[u]=++cnt;
    deep[u]=deep[fa]+1;
    maxdeep=max(maxdeep,deep[u]);
    arr[deep[u]].push_back(u);
    inn[deep[u]].push_back(in[u]);
    for(auto i:edge[u]){
        dfs(i,u);
    }
    out[u]=cnt;
}
inline int lowbit(int x){return x&(-x);}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        edge[x].push_back(i);
    }
    cin>>s;
    //cout<<"dddddd"<<endl;
    dfs(1,0);
    //cout<<"dddddd"<<endl;
    for(int i=1;i<=maxdeep;i++){
        int y=0;
        for(auto j:arr[i]){
            int x=s[j-1]-'a';
            y^=(1<<x);
            b[i].push_back(y);
        }
    }
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        int l,r;
        l=lower_bound(inn[y].begin(),inn[y].end(),in[x])-inn[y].begin();
        r=upper_bound(inn[y].begin(),inn[y].end(),out[x])-inn[y].begin()-1;
        if(r<0){
            cout<<"Yes"<<endl;
            continue;
        }
        int z;
        if(l<1) z=b[y][r];
        else z=b[y][r]^b[y][l-1];
        z-=lowbit(z);
        if(!z) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}