fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
3
https://ideone.com/TiX7Dy
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

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!