fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 4e4 + 5; 
  12. const int Q = 1e5 + 5; 
  13. const int B = 282; // sqrt(2 * N)   
  14.  
  15. // Ở bài này ta sẽ áp dụng kiến thức Euler Tour cho Truy vấn Đường đi, kết hợp với Thuật toán Mo
  16. // Tham khảo Thuật toán Mo trên Cây (Mo's Algorithm on Trees [Tutorial] (blog Codeforces))
  17.  
  18. struct Query {
  19. 	int l, r, lca_uv, idx;  
  20. 	bool operator<(const Query &other) const {
  21. 		if (l / B == other.l / B) {
  22. 			return (l / B & 1) ? (r > other.r) : (r < other.r); 
  23. 		}
  24. 		return (l < other.l); 
  25. 	}
  26. }; 
  27.  
  28. int n, q;  
  29. int c[N]; 
  30. vector<int> adj[N]; 
  31.  
  32. void compress(int c[]) {
  33. 	vector<int> vals;  
  34. 	for (int u = 1; u <= n; u++) {
  35. 		vals.push_back(c[u]); 
  36. 	}
  37. 	sort(vals.begin(), vals.end()); 
  38. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 
  39. 	for (int u = 1; u <= n; u++) {
  40. 		c[u] = lower_bound(vals.begin(), vals.end(), c[u]) - vals.begin();
  41. 	}
  42. }
  43.  
  44. int up[16][N]; 
  45. int euler_tour[2 * N]; 
  46. int tin[N], tout[N], timer; 
  47.  
  48. void dfs(int u, int p) {
  49. 	tin[u] = ++timer;  
  50. 	euler_tour[timer] = u;  
  51. 	up[0][u] = p;   
  52. 	for (int i = 1; i <= 15; i++) {
  53. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  54. 	}
  55. 	for (int v : adj[u]) {
  56. 		if (v == p) continue;  
  57. 		dfs(v, u); 
  58. 	}
  59. 	tout[u] = ++timer; 
  60. 	euler_tour[timer] = u;  
  61. }
  62.  
  63. bool isAncestor(int u, int v) {
  64. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  65. }
  66.  
  67. int lca(int u, int v) {
  68. 	if (isAncestor(u, v)) return u; 
  69. 	if (isAncestor(v, u)) return v;
  70. 	for (int i = 15; i >= 0; i--) {
  71. 		if (!isAncestor(up[i][u], v)) {
  72. 			u = up[i][u]; 
  73. 		}
  74. 	}
  75. 	return up[0][u]; 
  76. }
  77.  
  78. vector<Query> queries;
  79. int cur_ans; // Số giá trị phân biệt hiện tại
  80. bool active[N]; // active[u] = 0/1: Đỉnh u có tham gia vào truy vấn hiện tại hay không 
  81. int cnt[N]; // cnt[val] = Số lần xuất hiện của giá trị val
  82. int ans[Q]; // ans[i] = Đáp án của truy vấn thứ i 
  83.  
  84. void add(int u) {
  85. 	cnt[c[u]]++; 
  86. 	cur_ans += (cnt[c[u]] == 1); 
  87. }
  88.  
  89. void remove(int u) {
  90. 	cnt[c[u]]--; 
  91. 	cur_ans -= (cnt[c[u]] == 0); 
  92. }
  93.  
  94. void update(int i) {
  95. 	int u = euler_tour[i]; 
  96. 	active[u] ^= 1; 
  97. 	if (active[u]) add(u); 
  98. 	else remove(u); 
  99. }
  100.  
  101. int main() {
  102. 	ios::sync_with_stdio(false); 
  103. 	cin.tie(nullptr); 	
  104. 	cin >> n >> q; 
  105. 	for (int u = 1; u <= n; u++) {
  106. 		cin >> c[u]; 
  107. 	}
  108. 	compress(c); 
  109.  
  110. 	for (int i = 0; i < n - 1; i++) {
  111. 		int u, v; 
  112. 		cin >> u >> v; 
  113. 		adj[u].push_back(v); 
  114. 		adj[v].push_back(u);  
  115. 	}
  116.  
  117. 	timer = 0;  
  118. 	dfs(1, 1);  
  119.  
  120. 	for (int i = 0; i < q; i++) {
  121. 		int u, v; 
  122. 		cin >> u >> v; 
  123. 		if (tin[u] > tin[v]) swap(u, v); 
  124. 		int lca_uv = lca(u, v); 
  125. 		if (u == lca_uv) {
  126. 			queries.push_back({tin[u], tin[v], -1, i}); 
  127. 		}
  128. 		else {
  129. 			queries.push_back({tout[u], tin[v], lca_uv, i}); 
  130. 		}
  131. 	}
  132.  
  133. 	sort(queries.begin(), queries.end());  
  134.  
  135. 	cur_ans = 0;  
  136. 	int cur_l = 1, cur_r = 0;  
  137. 	for (Query &q : queries) {
  138. 		while (cur_l < q.l) update(cur_l++); 
  139. 		while (cur_r > q.r) update(cur_r--);  
  140. 		while (cur_l > q.l) update(--cur_l); 
  141. 		while (cur_r < q.r) update(++cur_r); 
  142. 		if (q.lca_uv != -1) update(tin[q.lca_uv]);  
  143. 		ans[q.idx] = cur_ans;  
  144. 		if (q.lca_uv != -1) update(tin[q.lca_uv]); 
  145. 	}
  146.  
  147. 	for (int i = 0; i < q; i++) {
  148. 		cout << ans[i] << '\n'; 
  149. 	}
  150. }
Success #stdin #stdout 0s 6532KB
comments (?)
stdin
copy 
8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
7 8
stdout
copy 
4
4
https://ideone.com/vRWdWj
language:
C++14 (gcc 8.3)
created:
180 days 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!