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. template<typename T>
  12. void minimize(T& a, const T& b) {
  13. 	if (b < a) a = b; 
  14. }
  15.  
  16. template<typename T>
  17. void maximize(T& a, const T& b) {
  18. 	if (a < b) a = b;  
  19. }
  20.  
  21. // - Truy vấn đường đi với các phép toán như min, max, gcd, lcm,...
  22. // - Với mỗi đường đi (u, v) bất kỳ, ta luôn có thể chia thành hai phần:
  23. //   đường đi (u, lca(u, v)) và đường đi (v, lca(u, v))
  24. // => Do đó, ta chỉ cần giải quyết truy vấn đường đi có dạng (u, anc) với anc là tổ tiên của u
  25. // - Lưu ý: Các phép toán min, max, gcd, lcm..., không tồn tại phép toán ngược 
  26. //   nên ta không thể xử lý như với các phép toán +, *, ^ (đưa về truy vấn dạng (u, 1))
  27. // => Thay vào đó, ta có thể giải quyết bằng kĩ thuật Binary Lifting
  28. // - Ngoài ra các phép toán như min, max, gcd, lcm,... cũng có tính chất giao hoán, nên ta không cần quan tâm đến chiều đường đi như thế nào
  29. const int N = 1e5 + 5; 
  30. const int LOG = 17;  
  31.  
  32. int n, q; 
  33. vector<ii> adj[N]; 
  34.  
  35. int depth[N]; 
  36. int up[LOG][N]; // up[i][u] = Tổ tiên thứ 2^i của u 
  37. int min_w[LOG][N]; // min_w[i][u] = Trọng số của cạnh nhỏ nhất trên đường đi (u, up[i][u])
  38. int max_w[LOG][N]; // max_w[i][u] = Trọng số của cạnh lớn nhất trên đường đi (u, up[i][u]) 
  39. int tin[N], tout[N], timer; 
  40.  
  41. void dfs(int u, int p) {
  42. 	tin[u] = ++timer; 
  43. 	up[0][u] = p;   
  44. 	for (int i = 1; i < LOG; i++) {
  45. 		up[i][u] = up[i - 1][up[i - 1][u]];  
  46. 		min_w[i][u] = min(min_w[i - 1][u], min_w[i - 1][up[i - 1][u]]);
  47. 		max_w[i][u] = max(max_w[i - 1][u], max_w[i - 1][up[i - 1][u]]); 
  48. 	}
  49. 	for (auto e : adj[u]) {
  50. 		int v = e.first, w = e.second; 
  51. 		if (v == p) continue;  
  52. 		depth[v] = depth[u] + 1; 
  53. 		min_w[0][v] = max_w[0][v] = w;  
  54. 		dfs(v, u); 
  55. 	}
  56. 	tout[u] = timer;  
  57. }
  58.  
  59. bool isAncestor(int u, int v) {
  60. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]);  
  61. }
  62.  
  63. int lca(int u, int v) {
  64. 	if (isAncestor(u, v)) return u;  
  65. 	if (isAncestor(v, u)) return v;  
  66. 	for (int i = LOG - 1; i >= 0; i--) {
  67. 		if (!isAncestor(up[i][u], v)) {
  68. 			u = up[i][u]; 
  69. 		}
  70. 	}
  71. 	return up[0][u]; 
  72. }
  73.  
  74. int getMin(int u, int anc) {
  75. 	int ans = INF; 
  76. 	int diff = depth[u] - depth[anc]; 
  77. 	for (int i = LOG - 1; i >= 0; i--) {
  78. 		if ((diff >> i) & 1) {
  79. 			minimize(ans, min_w[i][u]);  
  80. 			u = up[i][u]; 
  81. 		}
  82. 	}
  83. 	return ans; 
  84. }
  85.  
  86. int getMax(int u, int anc) {
  87. 	int ans = 0; 
  88. 	int diff = depth[u] - depth[anc]; 
  89. 	for (int i = LOG - 1; i >= 0; i--) {
  90. 		if ((diff >> i) & 1) {
  91. 			maximize(ans, max_w[i][u]);  
  92. 			u = up[i][u]; 
  93. 		}
  94. 	}
  95. 	return ans; 
  96. }
  97.  
  98. int main() {
  99. 	ios::sync_with_stdio(false); 
  100. 	cin.tie(nullptr); 	
  101. 	cin >> n; 
  102. 	for (int i = 0; i < n - 1; i++) {
  103. 		int u, v, w; 
  104. 		cin >> u >> v >> w; 
  105. 		adj[u].push_back({v, w}); 
  106. 		adj[v].push_back({u, w}); 
  107. 	}
  108. 	cin >> q;   
  109.  
  110. 	timer = 0;  
  111. 	depth[1] = 0; 
  112. 	dfs(1, 1);   
  113.  
  114. 	while (q--) {
  115. 		int u, v; 
  116. 		cin >> u >> v; 
  117. 		int lca_uv = lca(u, v);  
  118. 		int mn = min(getMin(u, lca_uv), getMin(v, lca_uv));  
  119. 		int mx = max(getMax(u, lca_uv), getMax(v, lca_uv)); 
  120. 		cout << mn << ' ' << mx << '\n'; 
  121. 	}
  122. }
Success #stdin #stdout 0.01s 22400KB
comments (?)
stdin
copy 
5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
stdout
copy 
100 200
50 150
50 100
https://ideone.com/4zQ5OZ
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!