看到这题就想到之前做过的一道字符串异或判断是否经过排列能形成回文结构。
可惜没想到用vector来维护相同深度的节点，以及使用in/out判断是否位于子树内的特殊操作。
甚至蛮好理解？
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<string>
5 #include<cmath>
6 #include<vector>
7 #define se second
8 #define fi first
9 using namespace std;
10 const int N = 5e5 + 10;
11 typedef pair<int, int> pii;
12 vector<int> v[N];
13 vector<pii> res[N];
14 int in[N];
15 int out[N];
16 int Hash[N];
17 int t = 0, n, m;
18 string s;
19
20 int read(){
21 char ch=getchar();int x=0,f=1;
22 while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
23 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
24 return x*f;
25 }
26
27 inline void dfs1(int u, int h)
28 {
29 in[u] = ++t;
30 res[h].push_back(make_pair(in[u], res[h].back().se ^ Hash[u]));
31 for(int i = 0 ; i < v[u].size() ; i++){
32 dfs1(v[u][i], h + 1);
33 }
34 out[u] = ++t;
35 return ;
36 }
37
38 int main(){
39 n = read();
40 m = read();
41 for(int i = 0 ; i <= n ; i++){
42 res[i].resize(1);
43 }
44 for(int i = 2 ; i <= n ; i++){
45 int p = read();
46 v[p].push_back(i);
47 }
48 cin >> s;
49 for(int i = 0 ; i < n ; i++){
50 Hash[i + 1] = (1 << (s[i] - 'a'));
51 }
52
53 dfs1(1, 1);
54
55 for(int i = 1 ; i <= m ; i++){
56 int v = read();
57 int h = read();
58 int l = lower_bound(res[h].begin(), res[h].end(), make_pair(in[v], -1)) - res[h].begin() - 1;
59 int r = upper_bound(res[h].begin(), res[h].end(), make_pair(out[v], -1)) - res[h].begin() - 1;
60 int tmp = res[h][l].se ^ res[h][r].se;
61 bool flag = tmp - (tmp & -tmp);
62 if(!flag) printf("Yes\n");
63 else printf("No\n");
64 }
65
66 return 0;
67 }