题意：对于m次询问 求解以vi为根节点 深度为hi的的字母能不能组合成回文串。
思路：暴力dsu找一边 简直就是神技！
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const int N=500007; const ll mod=1e9+7; struct node{ int h,id; bool f; friend bool operator < (node a,node b){ return a.id<b.id; } }; vector<int> G[N]; char val[N]; int dp[N],son[N],cnt[N][26]; int odd[N]; int de[N]; int po=0; vector<node> h[N]; node ans[N]; void dfs(int u,int fa,int deep){ dp[u]=1; de[u]=deep; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==fa) continue; dfs(v,u,deep+1); dp[u]+=dp[v]; if(dp[v]>dp[son[u]]) son[u]=v; //树剖 } } void add(int u,int fa,int w,int deep){ cnt[deep][val[u]-'a']+=w; if(cnt[deep][val[u]-'a']&1) odd[deep]++; else odd[deep]--; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==fa||v==po) continue; add(v,u,w,deep+1); } } int num=0; void dfss(int u,int fa,int opt,int deep){ for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==fa) continue; if(v!=son[u]) dfss(v,u,0,deep+1); } if(son[u]) dfss(son[u],u,1,deep+1),po=son[u]; add(u,fa,1,deep); po=0; for(int i=0;i<h[u].size();i++){ node tmp=h[u][i]; if(odd[tmp.h]>=2) tmp.f=0; ans[++num]=tmp; } if(!opt) add(u,fa,-1,deep); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=2;i<=n;i++){ int fa; cin>>fa; G[fa].push_back(i); } for(int i=1;i<=n;i++){ cin>>val[i]; } for(int i=1;i<=m;i++){ int vi,hi; cin>>vi>>hi; node tmp; tmp.h=hi; tmp.f=1; tmp.id=i; h[vi].push_back(tmp); } dfs(1,0,1); dfss(1,0,1,1); sort(ans+1,ans+1+m); for(int i=1;i<=num;i++){ if(ans[i].f) cout<<"Yes "; else cout<<"No "; } return 0; }