fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. #define N 500100
  5. ll n,x,y,q,d,Depth[N];
  6. vector<ll> Adj[N];
  7. string s;
  8. map<ll,ll> Res[N],Ret[N];
  9. map<ll, map<char,bool> > my[N];
  10. void add(ll u,ll depth,map<char,bool > mp)
  11. {
  12.     for(auto p : mp)
  13.     {
  14.         Res[u][depth]+=(my[u][depth][p.first] ? -1 : +1);
  15.         my[u][depth][p.first]=! my[u][depth][p.first];
  16.     }
  17. }
  18. void Merge(ll u,ll v)
  19. {
  20. 	if(my[u].size() < my[v].size())
  21.     {
  22.         swap(Res[u],Res[v]);
  23.         swap(my[u],my[v]);
  24.     }
  25.     for(auto p  :  my[v])
  26.         add(u,p.first,p.second);
  27.     Ret[u]=Res[u];
  28. }
  29. void Dfs(ll u,ll par)
  30. {
  31.     for(ll v : Adj[u])
  32.     {
  33.         if(v==par)  continue;
  34.         Dfs(v,u);
  35.         Merge(u,v);
  36.     }
  37. }
  38. void getDepth(ll u,ll par)
  39. {
  40.     Depth[u]=Depth[par]+1;
  41.     for(ll v: Adj[u])
  42.         if(v!=par)
  43.             getDepth(v,u);
  44. }
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0);
  48.     cin>>n>>q;
  49.     for(ll i=2 ; i<=n ; i++)
  50.     {
  51.         cin>>x;
  52.         Adj[x].push_back(i);
  53.         Adj[i].push_back(x);
  54.     }
  55.     getDepth(1,0);
  56.     cin>>s;
  57.     for(ll i=1  ; i<=n; i++)    my[i][Depth[i]][s[i-1]]=1   ,   Res[i][Depth[i]]++;
  58.     Dfs(1,-1);
  59.     while(q--)
  60.     {
  61.         cin>>x>>d;
  62.         cout<<(Ret[x][d]<=1 ? "Yes"  : "No")<<endl;
  63.     }
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.03s 85552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/APAhFp
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!