题解 CF570D 【Tree Requests】

牛蛙丶丶 · 2020-11-01 13:50:04 · 题解

dsu on tree 练习题

首先，因为是以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串，要排列后成为回文串，所以在符合条件的所有字母之中必须至多只有一种字母的数量为奇数种。

然后，就是基本的 dsu on tree 的操作了，先将所有的询问以离线的方式存储下来，这样子做可以让我们一边dfs，一边解决所有的询问，之后统计所有深度字母的出现次数以便我们的 check ，再将轻边子树的信息保留到重链之上进行一个答案的统计。

code

#include <cstdio>
#include <algorithm>
#include <vector>
#define N 500070

struct Tree{
    int to,nxt;
}e[N<<1];
struct Rec{
    int k,id;
};
int n,m,cnt;
int head[N],sz[N],sum[N],son[N],dep[N],ans[N],tot[N][26];
bool vis[N];
std::vector<Rec>q[N];
char s[N];

void add(int from,int to){e[++cnt].to=to,e[cnt].nxt=head[from],head[from]=cnt;}
void dfs(int x,int fa){
    sz[x]=1,dep[x]=dep[fa]+1;
    for(int i=head[x],v;i;i=e[i].nxt){
        v=e[i].to;if(v==fa) continue;
        dfs(v,x),sz[x]+=sz[v];
        if(!son[x]||sz[v]>sz[son[x]]) son[x]=v;
    }
}
void calc(int x,int fa,int val){
    tot[dep[x]][s[x]-'a']+=val;
    for(int i=head[x],v;i;i=e[i].nxt){
        v=e[i].to;if(v==fa||vis[v]) continue;
        calc(v,x,val);
    }
}
bool check(int s[]){
    int r=0;
    for(int i=0;i<26;++i){
        if(s[i]&1) ++r;
        if(r>1) return 0;
    }
    if(r>1) return 0;
    return 1;
}
void dfs2(int x,int fa,int keep){
    for(int i=head[x],v;i;i=e[i].nxt){
        v=e[i].to;if(v==fa||v==son[x]) continue;
        dfs2(v,x,0);
    }
    if(son[x]) dfs2(son[x],x,1),vis[son[x]]=1;
    calc(x,fa,1),vis[son[x]]=0;
    for(int i=0;i<q[x].size();++i) ans[q[x][i].id]=check(tot[q[x][i].k]);
    if(!keep) calc(x,fa,-1);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=2,u;i<=n;++i){
        scanf("%d",&u);
        add(u,i),add(i,u);
    }
    scanf("%s",s+1);
    dfs(1,0);
    for(int i=1,a,b;i<=m;++i){
        scanf("%d%d",&a,&b);
        q[a].push_back((Rec){b,i});
    }
    dfs2(1,0,0);
    for(int i=1;i<=m;++i)
        puts(ans[i]?"Yes":"No");
}