fork download
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. #define N 400009
  6. #define M 800099
  7.  
  8. using namespace std;
  9.  
  10. int start[N] ;
  11. int en [N] ;
  12. int color[N] ;
  13. int E[M] ;
  14. int pos = 0 ;
  15.  
  16. vector <int> tree[N] ;
  17. long long int ST[4*M] ;
  18. int lazy[4*M] ;
  19.  
  20. void update(int i, int j, int low, int high, int pos, int value){
  21.  
  22. if (lazy[pos]){
  23.  
  24. if (pos % 2)
  25. ST[pos] = ST[pos / 2] ;
  26. else
  27. ST[pos] = ST[(pos / 2) - 1] ;
  28.  
  29. if (low != high){
  30. lazy[2*pos+1]++ ;
  31. lazy[2*pos+2]++ ;
  32. }
  33. lazy[pos] = 0 ;
  34.  
  35. }
  36.  
  37. if (i > high || j < low)
  38. return ;
  39. if (i <= low && high <= j){
  40.  
  41. ST[pos] = 1LL << value ;
  42. lazy[2*pos+1]++ ;
  43. lazy[2*pos+2]++ ;
  44. return ;
  45.  
  46.  
  47. }
  48. int mid = ((low+high) / 2) ;
  49.  
  50. update(i, j, low, mid, 2*pos+1, value) ;
  51. update(i, j, mid+1, high, 2*pos+2, value) ;
  52.  
  53. ST[pos] = ST[2*pos+1] | ST[2*pos+2] ;
  54.  
  55. }
  56.  
  57. long long int query(int i, int j, int low, int high, int pos){
  58.  
  59. if(lazy[pos]){
  60.  
  61. if (pos % 2)
  62. ST[pos] = ST[pos / 2] ;
  63. else
  64. ST[pos] = ST[(pos / 2) - 1] ;
  65. if (low != high){
  66.  
  67. lazy[2*pos+1]++ ;
  68. lazy[2*pos+2]++ ;
  69. }
  70. lazy[pos] = 0 ;
  71. }
  72.  
  73. if (i > high || j < low)
  74. return 0 ;
  75. if (i <= low && high <= j)
  76. return ST[pos] ;
  77.  
  78. int mid = (low+high) / 2 ;
  79. return (query(i, j, low, mid, 2*pos+1) | query(i, j, mid+1, high, 2*pos+2)) ;
  80. }
  81.  
  82. void ETT(int v, int pv){
  83.  
  84. E[pos] = v ;
  85. if (!start[v])
  86. start[v] = pos ;
  87. pos++ ;
  88.  
  89. for (int i = 0; i < tree[v].size(); i++){
  90.  
  91. int u = tree[v][i] ;
  92. if (u == pv)
  93. continue ;
  94. ETT(u, v) ;
  95. E[pos] = v ;
  96. pos ++ ;
  97. }
  98.  
  99. if (!en[v])
  100. en[v] = pos-1 ;
  101. }
  102.  
  103.  
  104. int main(){
  105. int n, m, x, y, L, R, count, value ;
  106. long long int ans ;
  107. cin >> n >> m ;
  108.  
  109. for (int i = 1; i <= n; i++)
  110. cin >> color[i] ;
  111.  
  112. for (int i = 0; i < n-1; i++){
  113. cin >> x >> y ;
  114. tree[x].push_back(y) ;
  115. tree[y].push_back(x) ;
  116. }
  117.  
  118.  
  119. ETT(1, 0) ;
  120.  
  121. /*for (int i = 0; i < 2*n-1; i++)
  122. cout << E[i] << " " ;
  123. cout << endl ;
  124. for (int i = 0; i <= n; i++)
  125. cout << start[i] << " ";
  126. cout << endl ;
  127. for (int i = 0; i <= n; i++)
  128. cout << en[i] << " " ;
  129. cout << endl;*/
  130.  
  131. for(int i = 1; i <=n ; i++)
  132. update(start[i], en[i], 0, 2*n-2, 0, color[i]) ;
  133.  
  134.  
  135. /*cout << endl ;
  136. for (int i = 0; i < 90; i++)
  137. cout << ST[i] << " " ;
  138. cout << endl;*/
  139.  
  140. for (int i = 0; i < m; i++){
  141.  
  142. cin >> x >> y ;
  143. L = start[y] ;
  144. R = en[y] ;
  145.  
  146. //cout << x << " " << y << endl ;
  147. //cout << L << " " << R << endl ;
  148. if (x == 2){
  149.  
  150. ans = query(L, R, 0, 2*n-2, 0) ;
  151. cout << __builtin_popcount(ans) << endl;
  152.  
  153. }
  154.  
  155. else{
  156.  
  157. cin >> value ;
  158. update(L, R, 0, 2*n-2, 0, value) ;
  159. /*cout << "here" << endl;
  160. for (int i = 0; i < 40; i++)
  161. cout << ST[i] << " " ;
  162. cout << endl ;*/
  163.  
  164. }
  165. }
  166.  
  167. return 0 ;
  168. }
Success #stdin #stdout 0s 53480KB
stdin
23 30
1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
4 11
6 12
6 13
7 14
7 15
7 16
8 17
8 18
10 19
10 20
10 21
11 22
11 23
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
stdout
6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
3