分析

本人只会两种做法——dsu on tree and 按深度处理
这里,我说一下码量比较小的第二种做法把(时间复杂度一样)

首先我们每次需要拉出来的是一棵子树内的深度为x的那些点
所以我们容易发现
能够被拉出来当且仅当,这个点深度为x
那么我们可以考虑维护每个深度的每种字母的dfn集合
然后就可以在的时间内拉出来当前询问的所有字母了
由于我们需要重新排序这些字母使之成为一个回文串
所以我们只能让个字母在使用数上为奇数
开一个cnt记录一下即可
时间复杂度:
期望得分:100分

代码

//CF570D
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

#define ll long long
#define cl(x, y) memset((x), (y), sizeof(x))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define de(x) cerr << #x << " = " << x << " "
#define inc_mod(x, y) x = ((x - y) % mod + mod) % mod
#define add_mod(x, y) x = (x + y) % mod
#define lowbit(x) (x & (-x))
#define inf 0x3f3f3f3f
#define mod 998244353
#define rson (x << 1 | 1)
#define lson (x << 1)
using namespace std;
const int maxn = 5e5 + 10;

int n, m, cnt_one, cnt_two, cnt;
vector<int> child[maxn];
int now, start[maxn], ed[maxn];
char num[maxn];
vector<int> bar[maxn][26];

inline void dfs(int a, int c) {
    start[a] = now;
    bar[c][num[a] - 'a'].push_back(now);
    now++;
    c++;
    rep(b, 0, int(child[a].size()) - 1) dfs(child[a][b], c);
    ed[a] = now;
}

int main() {
    scanf("%d %d",&n, &m);
    rep(a, 1, n - 1) {
        scanf("%d", &cnt_one);
        child[cnt_one - 1].push_back(a);
    }
    scanf("%s", num);
    dfs(0, 0);
    while(m--) {
        scanf("%d %d", &cnt_one, &cnt_two);
        cnt_one--; cnt_two--;
        cnt=0;
        rep(a, 0, 25) {
            int temp = lower_bound(bar[cnt_two][a].begin(), bar[cnt_two][a].end(), ed[cnt_one])-lower_bound(bar[cnt_two][a].begin(), bar[cnt_two][a].end(), start[cnt_one]);
            cnt += temp % 2;
        }
        if(cnt >= 2) printf("No\n");
        else printf("Yes\n");
    }
    system("pause");
    return 0;
}