使用数组表示当前子树内,深度字母为的有多少个
那么可以开始,这样与有关的所有询问都可以快速得出解
差不多就是板子了
储存询问用或链式前向星
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5+19; struct edge{ int to,nxt; }d[maxn]; int head[maxn],ccnt=1; struct asking{ int to,nxt; bool ans; }ask[maxn]; int qhead[maxn],num=1; void add(int u,int v) { d[++ccnt] = (edge){v,head[u]},head[u]=ccnt; } void addask(int u,int h) { ask[++num] = asking{h,qhead[u]},qhead[u] = num; } int siz[maxn],son[maxn],n,m; int cnt[maxn][30],deep[maxn]; char s[maxn]; bool isok(int dep) { int ji=0; for(int i=0;i<=25;i++) if( cnt[dep][i]%2==1 ) ji++; if( ji>1 ) return false; return true; } void dfs(int u,int fa) { siz[u] = 1; deep[u] = deep[fa]+1; for(int i=head[u];i;i=d[i].nxt ) { int v = d[i].to; if( v== fa ) continue; dfs(v,u); siz[u]+=siz[v]; if( siz[v]>siz[son[u]] ) son[u]=v; } } int SON; void take(int u,int fa,int val) { cnt[ deep[u] ][s[u]-'a']+=val; for(int i=head[u];i;i=d[i].nxt ) { int v = d[i].to; if( v==fa||v==SON ) continue; take(v,u,val); } } void dsu(int u,int fa,int clea) { for(int i=head[u];i;i=d[i].nxt ) { int v = d[i].to; if( v==son[u]||v==fa ) continue; dsu(v,u,0); } if( son[u] ) dsu(son[u],u,1),SON = son[u];//保存 take(u,fa,1); SON = 0; for(int i=qhead[u];i;i=ask[i].nxt ) { int dep = ask[i].to;//深度 ask[i].ans = isok(dep); } if( !clea ) take(u,fa,-1); } int main() { cin >> n >> m; for(int i=2;i<=n;i++) { int x; scanf("%d",&x); add(x,i); } scanf("%s",s+1); for(int i=1;i<=m;i++) { int v,h; scanf("%d%d",&v,&h); addask(v,h); } dfs(1,0); dsu(1,0,0); for(int i=2;i<=num;i++) printf(ask[i].ans?"Yes\n":"No\n"); }