fork(13) download
  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. s[x]=ch;
  66. }
  67. else if(cs==1)
  68. {
  69. int ct=0;
  70. scanf("%d",&x);
  71. for(int i=0;i<26;i++)
  72. {
  73. ll xx=qry(i,en[x])-qry(i,st[x]-1);
  74. if(xx&1) ct++;
  75. }
  76. if(ct==0 || ct==1)
  77. printf("YES\n");
  78. else
  79. printf("NO\n");
  80. }
  81. }
  82. return 0;
  83. }
Success #stdin #stdout 0s 5536KB
stdin
101
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
8 10
10 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20
8 21
7 22
7 23
7 24
7 25
7 26
7 27
7 28
7 29
7 30
7 31
7 32
7 33
7 34
7 35
7 36
7 37
7 38
6 39
6 40
6 41
6 42
6 43
6 44
6 45
6 46
6 47
6 48
6 49
6 50
6 51
6 52
5 53
5 54
5 55
5 56
5 57
5 58
5 59
5 60
5 61
5 62
5 63
5 64
5 65
4 66
4 67
4 68
4 69
4 70
4 71
4 72
4 73
4 74
4 75
4 76
4 77
4 78
4 79
4 80
4 81
4 82
3 83
3 84
3 85
3 86
3 87
3 88
3 89
3 90
2 91
2 92
2 93
2 94
2 95
2 96
1 97
1 98
1 99
1 100
1 101
audtbfcynchcpkqcvglnlxcnejyehlohitclbhkojtsydiazrnmckqprzpxgclpmfuaibmwkfpkizmhqavumojdpacydonpvjpdkb
1000
1 49
0 45 g
1 45
1 31
0 92 w
1 68
0 5 n
1 34
1 94
0 90 p
1 47
0 14 h
1 39
1 58
1 86
0 73 x
1 3
0 83 e
1 50
0 30 e
0 63 w
1 7
1 87
0 93 n
1 100
0 76 c
1 55
0 26 s
1 65
1 10
0 76 e
0 33 m
0 13 o
0 38 l
0 25 x
0 100 o
1 32
1 73
0 29 a
0 55 h
0 88 x
1 64
1 14
1 18
1 12
0 95 m
1 83
0 39 e
1 37
1 55
1 66
1 38
1 30
0 30 h
1 1
0 47 v
1 46
1 30
0 72 l
1 53
1 30
0 20 p
0 13 t
1 79
0 78 r
1 22
0 68 e
0 80 h
0 58 m
1 87
1 35
1 63
0 67 b
0 86 s
0 98 o
1 28
0 23 h
0 96 v
1 1
0 21 b
0 30 n
1 16
0 64 q
0 2 i
0 30 z
0 88 j
0 33 w
1 8
1 44
0 38 q
0 20 g
1 90
0 62 a
1 22
1 83
0 35 o
0 16 o
0 3 x
1 87
1 61
1 88
1 49
0 92 s
1 100
0 37 j
1 55
1 99
1 26
0 26 r
0 41 f
1 95
0 9 m
0 21 w
1 76
0 72 s
0 19 j
0 55 v
1 61
0 25 p
1 15
0 81 b
0 47 o
0 5 e
0 65 y
0 12 h
0 35 b
1 5
0 36 u
1 62
0 28 f
1 3
1 50
1 67
1 30
0 84 z
0 83 w
0 59 v
1 14
0 51 o
0 74 z
1 3
0 86 o
1 60
0 42 s
1 60
0 97 k
1 83
0 96 u
1 7
1 57
1 98
1 24
0 33 q
1 35
1 3
0 5 d
1 98
0 69 n
0 66 x
1 100
1 18
1 91
1 85
1 95
0 55 l
0 39 d
1 73
0 56 v
1 70
0 5 t
0 14 t
1 37
0 79 s
1 66
0 13 c
1 7
0 12 b
0 50 f
1 75
1 29
1 65
1 10
1 45
1 35
1 52
1 69
1 92
1 48
1 71
1 8
0 82 s
0 2 y
1 75
0 21 s
1 38
0 75 k
0 98 w
0 1 j
0 83 s
1 30
0 100 e
1 29
1 90
0 13 d
1 39
1 68
0 25 e
0 51 q
1 1
1 6
0 23 r
0 82 s
1 42
0 42 m
0 53 r
0 17 x
1 7
0 85 b
1 42
1 50
1 9
1 63
1 3
1 91
0 19 z
0 60 x
1 20
1 99
0 8 y
1 25
1 3
0 77 t
1 32
0 58 c
0 72 r
0 57 a
0 27 b
0 86 y
0 57 t
0 26 a
0 57 o
1 11
0 6 x
0 38 w
1 30
0 11 s
0 20 u
0 46 v
1 84
1 54
1 13
1 17
0 96 x
0 26 b
1 83
1 84
1 70
0 1 n
0 36 x
1 70
1 2
1 99
0 77 p
1 42
0 41 v
0 18 c
1 5
1 2
1 59
1 77
0 74 v
0 61 s
0 83 c
1 84
0 58 v
0 33 a
0 25 w
0 42 a
1 99
1 32
1 10
0 83 l
1 50
1 43
0 82 e
0 7 l
0 16 g
0 49 j
1 73
1 64
0 2 v
0 53 a
1 62
0 4 m
1 54
1 4
1 98
1 86
1 39
1 72
1 41
1 37
1 44
1 57
1 67
1 78
0 26 x
1 58
0 34 t
1 49
0 45 t
0 30 r
0 34 w
1 74
1 98
0 91 c
0 53 i
0 30 s
1 29
1 16
1 63
0 91 h
0 88 a
0 69 t
1 2
1 33
0 33 a
0 24 e
1 28
1 4
0 20 u
1 50
1 21
1 14
0 27 y
1 88
0 19 u
1 72
0 61 e
0 43 s
1 35
1 21
1 21
1 80
1 19
0 9 e
1 23
0 23 s
0 10 e
0 10 s
1 48
0 46 i
0 93 d
0 10 c
0 83 l
1 16
1 48
1 26
0 98 p
0 2 l
1 63
1 36
0 56 k
0 53 u
0 45 y
0 7 c
0 41 p
1 56
0 23 a
1 66
0 67 n
1 3
1 96
1 95
1 17
0 96 d
1 36
1 54
0 24 v
0 64 k
0 71 i
0 2 t
1 34
1 6
0 56 g
0 18 s
1 86
0 56 q
1 91
0 25 w
1 86
1 64
1 44
1 22
1 87
0 26 d
0 83 g
1 99
0 91 g
1 77
0 15 k
0 58 m
0 4 s
0 63 j
1 58
0 78 r
1 38
0 69 n
0 7 f
0 7 l
0 67 f
0 33 q
0 90 e
1 94
0 16 z
1 71
1 91
1 25
1 38
0 8 a
0 15 f
0 73 r
0 91 w
0 24 m
1 13
1 29
1 2
1 18
1 14
0 24 l
0 63 a
0 22 a
0 36 i
0 9 b
0 99 x
0 74 m
1 39
1 14
1 77
0 65 p
0 99 s
1 57
0 42 u
0 84 w
1 44
0 68 a
0 19 a
1 92
0 15 d
1 81
1 34
0 94 h
0 93 z
1 1
0 95 h
0 79 d
1 74
0 78 s
0 96 u
1 87
0 95 e
1 75
1 45
0 91 b
1 35
1 35
1 2
1 71
1 8
1 13
0 54 j
0 57 c
0 36 d
0 82 h
1 8
0 73 i
0 64 p
1 35
1 57
1 19
0 39 l
1 4
0 72 k
0 80 n
1 15
0 92 w
1 72
1 84
1 78
1 59
0 83 v
0 91 k
0 17 p
0 35 q
0 58 a
0 89 p
1 3
1 4
0 43 u
0 26 p
1 92
1 21
1 21
0 17 d
0 85 s
0 71 k
0 80 m
1 68
0 89 y
1 92
0 59 f
0 84 u
0 27 q
0 5 i
0 73 l
0 9 f
1 80
1 20
0 35 k
0 51 n
0 66 a
0 24 g
1 60
0 82 x
0 72 j
1 56
1 69
1 75
0 57 r
1 77
1 32
0 46 z
1 98
1 91
0 23 g
1 82
0 71 f
1 42
0 41 q
0 9 l
0 93 q
1 43
0 73 f
0 19 h
0 68 e
0 46 s
0 35 c
0 57 j
1 98
1 42
1 28
0 72 n
0 54 o
0 16 p
0 50 d
1 98
0 32 h
0 12 r
0 78 m
1 63
1 89
0 92 c
1 94
1 20
1 63
1 77
1 21
0 79 v
1 77
0 95 r
0 58 l
0 36 x
1 50
0 21 x
1 7
1 55
1 21
0 78 j
0 59 c
0 37 x
1 65
1 18
0 64 g
1 53
1 71
1 12
0 52 i
0 58 f
0 25 p
0 54 b
0 12 d
0 1 a
1 65
0 21 i
1 48
1 14
0 68 j
1 9
0 49 a
0 74 i
0 20 d
0 49 h
1 78
0 100 p
1 17
1 47
0 22 j
0 87 b
1 36
1 86
0 82 v
0 55 g
0 26 j
0 74 s
0 3 m
1 65
0 84 r
0 97 o
1 55
1 73
1 23
1 18
0 87 a
0 94 g
1 19
1 54
0 3 t
0 53 x
0 29 u
0 99 u
0 66 c
1 39
0 1 d
1 11
0 96 h
1 83
0 46 p
1 90
1 28
0 15 o
0 43 i
0 94 f
1 59
1 61
0 62 k
0 93 b
0 41 k
1 23
0 95 p
1 37
1 75
0 54 w
0 48 f
1 41
0 59 t
1 19
1 78
1 96
1 55
1 10
0 23 b
0 70 t
1 58
0 57 x
1 51
1 53
1 39
1 58
0 97 f
1 48
0 99 d
1 5
0 30 y
1 13
0 9 t
1 66
1 20
0 31 w
1 84
1 5
0 74 m
0 47 p
1 97
1 19
1 26
1 97
1 27
1 8
0 35 d
1 13
0 54 y
0 19 j
0 75 p
1 80
1 56
0 54 j
0 72 q
1 59
1 72
0 29 e
0 15 j
1 27
0 31 p
0 2 y
0 28 o
1 7
1 9
1 83
1 30
0 31 q
0 50 z
1 78
0 28 r
1 6
0 78 x
1 91
0 34 a
0 34 i
0 12 q
1 46
0 65 f
0 92 c
1 93
1 69
0 49 b
0 6 l
1 94
0 22 h
0 9 j
1 49
0 99 g
1 45
0 29 l
0 72 n
1 64
0 62 e
1 74
0 43 i
1 36
1 48
1 26
1 23
0 56 a
1 52
0 56 w
0 3 e
1 67
0 85 a
1 73
1 39
0 83 p
0 70 k
1 91
1 99
1 54
1 68
0 5 l
1 65
1 75
1 5
0 80 f
0 97 b
0 36 u
0 81 k
1 97
1 81
1 66
1 91
0 17 j
0 55 c
1 90
0 67 g
0 98 n
1 94
0 78 o
0 98 o
0 39 y
1 71
1 45
1 37
0 85 t
1 39
1 29
1 27
0 74 k
1 13
1 89
1 91
1 54
1 82
0 79 q
1 1
1 43
0 24 y
0 19 h
0 93 j
1 19
1 100
0 15 z
0 4 o
0 25 m
0 58 k
0 48 h
0 36 p
0 11 q
0 30 x
0 74 h
0 92 y
1 84
1 25
1 65
1 35
0 92 e
1 96
0 46 e
0 33 w
1 43
0 36 n
1 25
0 25 o
1 20
1 24
0 72 a
0 77 a
0 68 e
1 63
0 27 x
1 11
1 5
1 8
1 77
0 16 p
1 2
0 1 k
1 81
0 49 u
0 95 c
0 64 x
0 20 y
1 83
0 5 q
1 12
0 13 m
1 38
1 100
1 2
1 90
1 24
1 62
0 84 j
0 99 g
0 71 e
0 53 p
0 44 w
0 26 u
0 23 h
1 74
1 23
1 41
1 1
1 17
0 65 h
0 16 n
1 86
0 40 r
1 28
0 52 d
1 65
1 33
1 65
1 17
0 31 i
1 84
1 62
1 7
0 37 p
0 48 s
0 87 l
1 66
0 95 b
1 59
0 78 c
1 36
0 40 d
1 86
0 95 g
0 1 t
0 22 t
1 32
1 86
1 87
0 68 g
1 13
1 81
0 20 d
1 12
0 95 u
1 96
1 9
1 64
1 60
1 13
0 69 l
1 52
1 42
0 26 p
1 69
1 26
1 3
0 4 m
0 20 s
1 83
0 3 e
1 62
1 70
1 4
0 11 v
1 53
1 99
1 13
1 55
1 59
0 92 v
0 41 h
0 36 l
0 39 r
1 52
0 53 d
0 81 h
1 2
1 93
0 23 h
1 77
0 82 s
0 44 r
0 29 h
1 44
0 4 d
1 56
1 61
0 14 k
1 29
0 42 b
0 64 i
1 93
0 51 e
0 46 v
0 74 d
0 70 f
1 31
0 65 j
0 91 n
1 99
1 24
1 7
1 55
0 91 y
1 93
1 68
0 27 u
1 24
0 37 i
1 67
1 89
0 10 s
1 39
0 49 b
1 56
0 23 v
0 69 y
1 96
0 60 e
0 27 h
0 64 s
1 82
1 2
1 29
0 3 f
0 4 i
0 59 b
0 98 z
0 47 k
0 15 j
0 43 u
1 85
1 36
1 51
0 4 c
1 36
0 7 r
1 91
1 6
1 22
1 58
0 54 v
0 20 h
0 62 d
1 46
0 28 u
0 34 n
stdout
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES