Codeforces Round #316 (Div. 2) D计算在一棵子树内某高度的节点

题：https://codeforces.com/contest/570/problem/D

题意：给定一个以1为根的n个节点的树，每个点上有一个字母(a~z)，每个点的深度定义为该节点到1号节点路径上的点数.每次询问a,b查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.

分析：很明显是个树上启发式合并。显然，只要深度为bb结点的所有颜色中，至多有一种的数量为奇数就可以构成回文串了。

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

typedef long long ll;

const int M=5e5+;

int sz[M],son[M],deep[M],w[M],countt[M][],ans[M],vis[M];

char s[M];

vector<int>g[M];

vector<pair<int,int> >Q[M];

void dfs1(int u,int fa){

    sz[u]=;

    deep[u]=deep[fa]+;

    for(int i=;i<g[u].size();i++){

        int v=g[u][i];

        dfs1(v,u);

        sz[u]+=sz[v];

        if(sz[v]>sz[son[u]])

            son[u]=v;

    }

}

void update(int u,int k){

    countt[deep[u]][w[u]]+=k;

    for(int i=;i<g[u].size();i++){

        int v=g[u][i];

        if(!vis[v])

        update(v,k);

    }

}

void dfs2(int u,int sign){

    for(int i=;i<g[u].size();i++){

        int v=g[u][i];

        if(v!=son[u])

            dfs2(v,);

    }

    if(son[u])

        dfs2(son[u],),vis[son[u]]=;

    update(u,);

    for(int i=;i<Q[u].size();i++){

        int num=;

        int id=Q[u][i].first;

        int d=Q[u][i].second;

        for(int j=;j<;j++){

            if(countt[d][j]&)

                num++;

        }

        if(num>)

            ans[id]=;

        else

            ans[id]=;

    }

    vis[son[u]]=;

    if(!sign)

        update(u,-);

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    for(int u,i=;i<=n;i++){

        scanf("%d",&u);

        g[u].pb(i);

    }

    scanf("%s",s);

    for(int i=;i<n;i++)

        w[i+]=s[i]-'a';

    for(int u,v,i=;i<=m;i++){

        scanf("%d%d",&u,&v);

        Q[u].pb(make_pair(i,v));

    }

    dfs1(,);

    dfs2(,);

    for(int i=;i<=m;i++)

        if(ans[i])

            printf("Yes\n");

        else

            printf("No\n");

    return ;

}