fork download 
  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. // - Những bài truy vấn đường đi Không chỉ dừng lại ở những phép toán cơ bản như +, ^, min, max, gcd, lcm,... 
  12. //   mà có thể mở rộng ra những phép toán/hàm phức tạp hơn
  13. // - Ở bài này mỗi đỉnh ta sẽ có một vector lưu lại ID đã được sort của những người ở đỉnh này, chỉ giữ tối đa 10 phần tử
  14. // - Ta định nghĩa thêm hàm combine(a, b) là hàm gộp 2 vector a, b đã sort thành 1 vector cũng được sort, chỉ giữ tối đa 10 phần tử 
  15. const int N = 1e5 + 5; 
  16. const int LOG = 17;   
  17.  
  18. int n, m, q;  
  19. vector<int> c[N]; // c[u] = Danh sách ID đã được sort của những người ở đỉnh u 
  20. vector<int> adj[N]; 
  21.  
  22. int up[LOG][N]; // up[i][u] = Tổ tiên thứ 2^i của u  
  23. vector<int> IDs[LOG][N]; // IDs[i][u] = Danh sách ID đã được sort của những người nằm trên đường đi (u, up[i][u]) (không bao gồm up[i][u]) 
  24. int depth[N]; 
  25. int tin[N], tout[N], timer;  
  26.  
  27. vector<int> combine(const vector<int> &a, const vector<int> &b) {
  28. 	vector<int> ans(a.size() + b.size());  
  29. 	int i = 0, j = 0, k = 0;  
  30. 	while (i < a.size() && j < b.size()) {
  31. 		if (a[i] < b[j]) ans[k++] = a[i++]; 
  32. 		else ans[k++] = b[j++]; 
  33. 	}
  34. 	while (i < a.size()) ans[k++] = a[i++]; 
  35. 	while (j < b.size()) ans[k++] = b[j++]; 
  36. 	if (ans.size() > 10) ans.resize(10); 
  37. 	return ans; 
  38. }
  39.  
  40. void dfs(int u, int p) {
  41. 	tin[u] = ++timer; 
  42. 	up[0][u] = p;  
  43. 	for (int i = 1; i < LOG; i++) {
  44. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  45. 		IDs[i][u] = combine(IDs[i - 1][u], IDs[i - 1][up[i - 1][u]]); 
  46. 	}
  47. 	for (int v : adj[u]) {
  48. 		if (v == p) continue; 
  49. 		IDs[0][v] = c[v]; 
  50. 		depth[v] = depth[u] + 1; 
  51. 		dfs(v, u); 
  52. 	}
  53. 	tout[u] = timer; 
  54. }
  55.  
  56. bool isAncestor(int u, int v) {
  57. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  58. }
  59.  
  60. int lca(int u, int v) {
  61. 	if (isAncestor(u, v)) return u; 
  62. 	if (isAncestor(v, u)) return v;  
  63. 	for (int i = LOG - 1; i >= 0; i--) {
  64. 		if (!isAncestor(up[i][u], v)) {
  65. 			u = up[i][u]; 
  66. 		}
  67. 	}
  68. 	return up[0][u]; 
  69. }
  70.  
  71. vector<int> query(int u, int anc) {
  72. 	vector<int> ans; 
  73. 	int diff = depth[u] - depth[anc]; 
  74. 	for (int i = 0; i < LOG; i++) {
  75. 		if ((diff >> i) & 1) {
  76. 			ans = combine(ans, IDs[i][u]); 
  77. 			u = up[i][u]; 
  78. 		}
  79. 	}
  80. 	return ans; 
  81. }
  82.  
  83. int main() {
  84. 	ios::sync_with_stdio(false); 
  85. 	cin.tie(nullptr); 	
  86. 	cin >> n >> m >> q; 
  87. 	for (int i = 0; i < n - 1; i++) {
  88. 		int u, v; 
  89. 		cin >> u >> v; 
  90. 		adj[u].push_back(v); 
  91. 		adj[v].push_back(u); 
  92. 	}
  93.  
  94. 	for (int i = 1; i <= m; i++) {
  95. 		int u; cin >> u; 
  96. 		if (c[u].size() < 10) c[u].push_back(i); 
  97. 	}	
  98.  
  99. 	timer = 0;  
  100. 	depth[1] = 0;
  101. 	dfs(1, 1); 
  102.  
  103. 	while (q--) {
  104. 		int u, v, k; 
  105. 		cin >> u >> v >> k; 
  106.  
  107. 		int lca_uv = lca(u, v); 
  108. 		vector<int> ans = combine(query(u, lca_uv), query(v, lca_uv)); 
  109. 		ans = combine(ans, c[lca_uv]); 
  110.  
  111. 		k = min(k, (int)ans.size());  
  112. 		cout << k << ' '; 
  113. 		for (int i = 0; i < k; i++) {
  114. 			cout << ans[i] << ' '; 
  115. 		}
  116. 		cout << '\n'; 
  117. 	}
  118. }
Success #stdin #stdout 0.02s 55764KB
comments (?)
stdin 
5 4 5
1 3
1 2
1 4
4 5
2 1 4 3
4 5 6
1 5 2
5 5 10
2 3 3
5 3 1
stdout 
1 3 
2 2 3 
0 
3 1 2 4 
1 2
https://ideone.com/JhH4RR
language:
C++14 (gcc 8.3)
created:
174 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!