fork download
copy 
  1. #include<bits/stdc++.h>
  2. const int M=100005;
  3. using namespace std;
  4. typedef long long ll;
  5. ll bit[26][4*M],st[M],en[M];
  6. vector<int>v[M];
  7. int n,m,trm=0;
  8. void upd(int i,int id,int val)
  9. {
  10. 	while(id<=2*n)
  11. 	{
  12. 		bit[i][id]+=val;
  13. 		id+=id&-id;
  14. 	}
  15. }
  16. ll qry(int i,int id)
  17. {
  18. 	ll ans=0;
  19. 	while(id>0)
  20. 	{
  21. 		ans+=bit[i][id];
  22. 		id-=id&(-id);
  23. 	}
  24. 	return ans;
  25. }
  26. void dfs(int u,int p)
  27. {
  28. 	st[u]=++trm;
  29. 	for(auto x:v[u])
  30. 	{
  31. 		if(x!=p)
  32. 		dfs(x,u);
  33. 	}
  34. 	en[u]=trm;
  35. }
  36. int main()
  37. {
  38. 	char s[M];
  39. 	scanf("%d",&n);
  40. 	for(int i=0;i<n-1;i++)
  41. 	{
  42. 		int x,y;
  43. 		cin>>x>>y;
  44. 		v[x].push_back(y);
  45. 		v[y].push_back(x);
  46. 	}
  47. 	dfs(1,-1);
  48. 	scanf("%s",1+s);
  49. 	for(int i=1;i<=n;i++)
  50. 	{
  51. 		int x=s[i]-'a';
  52. 		upd(x,st[i],1);
  53. 	}
  54. 	scanf("%d",&m);
  55. 	while(m--)
  56. 	{
  57. 		int cs,x;
  58. 		char ch;
  59. 		scanf("%d",&cs);
  60. 		if(cs==0)
  61. 		{
  62. 			scanf("%d %c",&x,&ch);
  63. 			upd(s[x]-'a',st[x],-1);
  64. 			upd(ch-'a',st[x],1);
  65. 		}
  66. 		else if(cs==1)
  67. 		{
  68. 			int ct=0;
  69. 			scanf("%d",&x);
  70. 			for(int i=0;i<26;i++)
  71. 			{
  72. 				ll xx=qry(i,en[x])-qry(i,st[x]-1);
  73. 				if(xx&1) ct++;
  74. 			}
  75. 			if(ct==0 || ct==1)
  76. 			printf("YES\n");
  77. 			else
  78. 			printf("NO\n");
  79. 		}
  80. 	}
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 5560KB
comments (?)
stdin
copy 
3 
1 2
2 3
abc
7
1 1
0 1 b
1 1
1 2
0 2 c
1 2
1 3

1 3
stdout
copy 
NO
YES
NO
YES
YES
https://ideone.com/l3BFX0
language:
C++14 (gcc 8.3)
created:
7 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!