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 = 7e4 + 5; 
  12. const int LOG = 17;  
  13.  
  14. // Nhận xét: Hàm lca(u, v) cũng giống với các hàm như max, min hay gcd
  15. // Và trong bài cũng không có truy vấn update nên ta có thể dùng Sparse Table
  16. // Độ phức tạp: O(q * log2(n))
  17. // Còn nếu bài có thêm truy vấn update thì ta có thể dùng Segment Tree
  18. // Độ phức tạp: O(q * log^2(n))
  19. int n, q;  
  20. vector<int> adj[N]; 
  21.  
  22. int up[LOG][N]; 
  23. int tin[N], tout[N], timer;   
  24.  
  25. void dfs(int u, int p) {
  26. 	tin[u] = ++timer;   
  27. 	up[0][u] = p;
  28. 	for (int i = 1; i < LOG; i++) {
  29. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  30. 	}
  31. 	for (int v : adj[u]) {
  32. 		if (v == p) continue; 
  33. 		dfs(v, u); 
  34. 	}
  35. 	tout[u] = timer; 
  36. }
  37.  
  38. bool isAncestor(int u, int v) {
  39. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  40. }
  41.  
  42. int lca(int u, int v) {
  43. 	if (isAncestor(u, v)) return u;  
  44. 	if (isAncestor(v, u)) return v;  
  45. 	for (int i = LOG - 1; i >= 0; i--) {
  46. 		if (!isAncestor(up[i][u], v)) {
  47. 			u = up[i][u]; 
  48. 		}
  49. 	}
  50. 	return up[0][u]; 
  51. }
  52.  
  53. int f[LOG][N]; // f[k][u] = lca của các đỉnh u, u + 1, ..., u + 2^k - 1 
  54.  
  55. void precompute() {
  56. 	for (int u = 1; u <= n; u++) f[0][u] = u;  
  57.  
  58. 	for (int k = 1; (1 << k) <= n; k++) {
  59. 		for (int u = 1; u + (1 << k) - 1 <= n; u++) {
  60. 			f[k][u] = lca(f[k - 1][u], f[k - 1][u + (1 << (k - 1))]); 
  61. 		}
  62. 	}
  63. }
  64.  
  65. int getLCA(int l, int r) {
  66. 	int k = log2(r - l + 1); 
  67. 	return lca(f[k][l], f[k][r - (1 << k) + 1]); 
  68. }
  69.  
  70. int main() {
  71. 	ios::sync_with_stdio(false); 
  72. 	cin.tie(nullptr); 		
  73. 	cin >> n >> q; 
  74.  
  75. 	for (int i = 0; i < n - 1; i++) {
  76. 		int u, v; 
  77. 		cin >> u >> v; 
  78. 		adj[u].push_back(v); 
  79. 		adj[v].push_back(u); 
  80. 	}
  81.  
  82. 	timer = 0;  
  83. 	dfs(1, 1); 
  84.  
  85. 	precompute();   
  86.  
  87. 	while (q--) {
  88. 		int l, r;  
  89. 		cin >> l >> r;  
  90. 		cout << getLCA(l, r) << '\n'; 
  91. 	}
  92. }
Success #stdin #stdout 0.01s 11572KB
comments (?)
stdin
copy 
5 3
1 2
2 3
3 4
3 5
2 5
1 3
4 5
stdout
copy 
2
1
3
https://ideone.com/EUlUVH
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!