[Codeforces] 570D. Tree Requests

題目連結:http://codeforces.com/contest/570/problem/D

---

把詢問依照節點存好，接下來我們就可以對樹DFS，同時記錄一下他的深度與每個字母出現的次數，然後要把兩棵子樹的資訊合併起來時就用啟發式合併，而完成一棵子樹後就可以把每個詢問的答案填上去，而且我們只在意奇偶性，所以甚至還可以用位元運算壓掉一些常數，大概就這樣吧。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const int N = 500000 + 5;

vector<int> G[N];
char wh[N];
vector<PII> que[N];
int ans[N], dep[N];

void dfs(int, map<int,int>&);

int main(){
	int n, q; scanf("%d%d",&n,&q);
	dep[1]=1;
	for(int i=2;i<=n;i++){
		int x; scanf("%d", &x);
		G[x].PB(i);
		dep[i]=dep[x]+1;
	}
	scanf("%s", wh);
	for(int i=0;i<q;i++){
		int v, d; scanf("%d%d", &v, &d);
		if(d < dep[v]) continue;
		que[v].PB({d, i});
	}
	map<int,int> mp;
	dfs(1, mp);
	for(int i=0;i<q;i++){
		if(__builtin_popcount((unsigned)ans[i])<=1) puts("Yes");
		else puts("No");
	}
	return 0;
}

void dfs(int w, map<int,int>& mp){
	mp[dep[w]]^=(1<<(wh[w-1]-'a'));
	for(auto i: G[w]){
		map<int, int> tp;
		dfs(i, tp);
		if(tp.size() > mp.size()) mp.swap(tp);
		for(auto data: tp) mp[data.FF]^=data.SS;
	}
	for(auto i: que[w]){
		auto it = mp.find(i.FF);
		if(it!=mp.end()) ans[i.SS] ^= it->SS;
	}
}