[Codeforces \ # 316 D. Tree Requests] DFS 순서, 오프라인, 이분

[Codeforces \ # 316 D. Tree Requests] DFS 순서, 오프라인, 이분
1. 제목 링크
[Codeforces #316 D. Tree Requests]
2. 제목 설명
N 개의 노드 를 지정 한 나 무 는 노드 마다 26 개의 소문 자 중의 한 글자 에 대응 하고 노드 i 의 깊이 는 depi 로 기록 합 니 다.M 번 질문 을 할 때마다 노드 u 의 하위 트 리 (노드 u 포함) 의 모든 깊이 는 depi 의 노드 이 고 각각 해당 하 는 자 모 를 얻어 문자열 을 구성 합 니 다.이 꼬치 를 어떤 배열 에 따라 하나의 회 문 꼬치 를 구성 할 수 있 느 냐 고 물 었 다.
3. 문제 풀이 사고방식
어떤 문자열 의 특정한 배열 은 회 문 열 을 구성 할 수 있 으 며, 이 문자열 의 모든 문 자 는 홀수 번 의 종 수 ≤ 1 로 나타 나 므 로, bitset < 26 > 로 각 문자 의 출현 횟수 의 패 리 티 를 유지 할 수 있 습 니 다.먼저, 나무의 dfs 순 서 를 구 합 니 다. 즉, 각 노드 가 lb 에 들 어가 고 나 오 는 시간 번호 ub 를 구하 고 각 노드 의 깊이 를 구 합 니 다.이렇게 하면 [lb, ub] 으로 이 노드 를 뿌리 노드 로 하 는 서브 트 리 를 표시 할 수 있다.그리고 오프라인 에 대해 물 어보 고 깊이 에 따라 처리 해 주세요.같은 깊이 의 질문.이 깊이 에서 모든 노드 의 접두사 가 다 르 거나 합 쳐 집 니 다.그리고 이 깊이 에서 모든 노드 의 왼쪽 경계 2 점, 오른쪽 경계 에 다시 2 점 을 줍 니 다.그리고 2 점 으로 얻 은 값 이 다 르 거나 이 조회 의 답 을 얻 을 수 있 습 니 다.
4. 구현 코드

#include 
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 500000 + 5;
const int BITS = 26;

int n, m;
char s[MAXN];
struct Edge {
    int v, next;
} edge[MAXN];
int head[MAXN], tot;

struct Node {
    int dep, lb, ub, mxdep;
} node[MAXN];
int nid;

vector<int> H[MAXN];

struct Query {
    int id, u;
};
vector I[MAXN];
bool Ans[MAXN];

void init() {
    tot = 0; nid = 0;
    memset(head, -1, sizeof(head));
    for(int i = 0; i < MAXN; i++) H[i].clear(), I[i].clear();
}

void add_edge(int u, int v) {
    edge[tot] = Edge{v, head[u]};
    head[u] = tot ++;
}

void dfs(int u, int k) {
    node[u].mxdep = node[u].dep = k;
    node[u].lb = ++ nid;
    H[k].push_back(u);
    for(int i = head[u], v; ~i; i = edge[i].next) {
        v = edge[i].v;
        dfs(v, k + 1);
        node[u].mxdep = max(node[u].mxdep, node[v].mxdep);
    }
    node[u].ub = nid;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
    scanf("%d %d", &n, &m);

    init();
    for(int u, v = 2; v <= n; v++) {
        scanf("%d", &u);
        add_edge(u, v);
    }

    scanf("%s", s + 1);

    dfs(1, 1);

    for(int i = 0, u, h; i < m; i++) {
        scanf("%d %d", &u, &h);
        I[h].push_back(Query{i, u});
    }
    vector<int> L(MAXN), R(MAXN);
    vector<bitset > pre(MAXN);
    for(int h = 0; h < MAXN; h++) {
        int sz = I[h].size(), hsz = H[h].size();
        if(sz == 0) continue;

        pre[0].reset();
        for(int i = 0; i < hsz; i++) {
            int& u = H[h][i];
            L[i] = node[u].lb;
            R[i] = node[u].ub;
            pre[i + 1] = pre[i];
            pre[i + 1].flip(s[u] - 'a');
        }
        for(int i = 0; i < sz; i++) {
            int& id = I[h][i].id, &u = I[h][i].u;
            if(hsz == 0) Ans[id] = true;
            else if(node[u].dep >= h) Ans[id] = true;
            else if(node[u].mxdep < h) Ans[id] = true;
            else {
                int &lb = node[u].lb, &ub = node[u].ub;
                int LB = lower_bound(L.begin(), L.begin() + hsz, lb) - L.begin();
                int UB = upper_bound(R.begin(), R.begin() + hsz, ub) - R.begin() - 1;
                if(LB > UB) {
                    Ans[id] = true;
                    continue;
                }
                bitset bs = pre[UB + 1] ^ pre[LB];
                if(bs.count() <= 1) Ans[id] = true;
                else Ans[id] = false;
            }
        }
    }
    for(int i = 0; i < m; i++) {
        puts(Ans[i] ? "Yes" : "No");
    }
    return 0;
}