CF570D Tree Requests 树上启发式合并

题目链接：luogu.com.cn/problem/CF570D
题目大意：

思路：轻重链启发式合并，cut[i][j]:维护深度为i的j单词个数。如果查询时，有<=1的单词个数为奇数就可以组成回文串。

 #include <bits/stdc++.h>
using namespace std;

char s[500005], c[500005];
vector<int> G[500005];
vector<pair<int, int> > q[500005];
int siz[500005], son[500005], dfn[500005], pos[500005], d[500005], cut[500005][26], T=0;
//pos：dfs序为i的节点
//c：i节点的词
int ans[500005];
void dfs(int u, int fa, int deep){
    siz[u]=1; dfn[u]=++T, pos[T]=u; d[u]=deep;
    for(auto x: G[u]){
        if(x!=fa){
            dfs(x, u, deep+1);
            siz[u]+=siz[x];
            son[u]=siz[x]>siz[son[u]]?x:son[u];
        }
    }
}

void DFS(int u, int fa, int k){
    for(auto x: G[u]){
        if(x!=fa&&x!=son[u]){
            DFS(x, u, 0);
        }
    }
    if(son[u]) DFS(son[u], u, 1);
    for(auto x: G[u]){
        if(x!=fa&&x!=son[u]){
            for(int i=0; i<siz[x]; i++){
                int nowson=pos[dfn[x]+i];
                cut[d[nowson]][c[dfn[nowson]]]++;
            }
        }
    }
    cut[d[u]][c[dfn[u]]]++;
    for(auto x: q[u]){
        int s=0;
        int deep=x.first;
        for(int i=0; i<26; i++){
            if(cut[deep][i]%2){
                s++;
            }
        }
        if(s<=1){
            ans[x.second]=1;
        }
    }
    if(!k){
        for(int i=0; i<siz[u]; i++){
            int nowson=pos[dfn[u]+i];
            for(int k=0; k<26; k++){
                cut[d[nowson]][k]=0;
            }
        }
    }
}

int main(){
    int n, m, x, y; scanf("%d%d", &n, &m);
    for(int i=2; i<=n; i++){
        scanf("%d", &x);
        G[x].push_back(i);
        G[i].push_back(x);
    }
    dfs(1, 0, 1);
    scanf("%s", s+1);
    for(int i=1; i<=n; i++){
        c[dfn[i]]=s[i]-'a';
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        q[x].push_back({y, i});
    }
    DFS(1, 0, 0);
    for(int i=1; i<=m; i++){
        if(ans[i]) printf("Yes\n");
        else printf("No\n");
    }
}