1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
|
#include <algorithm> #include <cstring> #include <vector> using namespace std; int u[500100<<1],v[500100<<1],fir[500100],nxt[500100<<1],cnt,val[500100],w_p[500100],sz[500100],vis[500100],heason[500100],ans[500100],dep[500100],n,m; struct { int b,pid; }; vector<ansNode> Vec[500100]; int calbit(int x){ int ans=0; while(x){ ans++; x&=(x-1); } return ans; } void change(int u,int f){ val[dep[u]]^=(1<<w_p[u]); for(int i=fir[u];i;i=nxt[i]){ if(vis[v[i]]||v[i]==f) continue; change(v[i],u); } } void addedge(int ui,int vi){ ++cnt; u[cnt]=ui; v[cnt]=vi; nxt[cnt]=fir[ui]; fir[ui]=cnt; } void dfs1(int u,int f){ sz[u]=1; dep[u]=dep[f]+1; for(int i=fir[u];i;i=nxt[i]){ if(v[i]==f) continue; dfs1(v[i],u); sz[u]+=sz[v[i]]; if(heason[u]==0||sz[heason[u]]<sz[v[i]]) heason[u]=v[i]; } } void dfs2(int u,int f,int islight){ for(int i=fir[u];i;i=nxt[i]){ if(v[i]==f||v[i]==heason[u]) continue; dfs2(v[i],u,1); } if(heason[u]) dfs2(heason[u],u,0),vis[heason[u]]=true; change(u,f); for(int i=0;i<Vec[u].size();i++) ans[Vec[u][i].pid]=(calbit(val[Vec[u][i].b])==1||calbit(val[Vec[u][i].b])==0); if(heason[u]) vis[heason[u]]=false; if(islight) change(u,f); } int main(){ dep[0]=0; scanf("%d %d",&n,&m); for(int i=2;i<=n;i++){ int x; scanf("%d",&x); addedge(x,i); addedge(i,x); } for(int i=1;i<=n;i++){ char c=getchar(); while(c<'a'||c>'z') c=getchar(); w_p[i]=c-'a'; } for(int i=1;i<=m;i++){ int x,y; scanf("%d %d",&x,&y); Vec[x].push_back((ansNode){y,i}); } dfs1(1,0); dfs2(1,0,0); for(int i=1;i<=m;i++) printf("%sn",(ans[i])?"Yes":"No"); return 0; }
|
近期评论