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. // - Đây là một bài Educational
  12. // - Gọi lca(u, v, root) là lca của 2 đỉnh u, v khi gốc của cây là root
  13. // - Ta có lca(u, v, root) = đỉnh sâu nhất trong 3 đỉnh lca(u, v, 1), lca(u, root, 1), lca(v, root, 1) 
  14. // - Cũng có thể chứng minh qua việc liệt kê ra một số trường hợp trên giấy với cây nhỏ: 
  15. //   u và v cùng thuộc cây con gốc root, chỉ u hoặc v thuộc cây con gốc root, u và v cùng nằm ngoài cây con gốc root.
  16. // - Đặc biệt trong 3 đỉnh đã nêu thì sẽ có ít nhất 2 đỉnh trùng nhau nên ta có thể viết ngắn gọn lại kết quả như sau:
  17. //   lca(u, v, root) = lca(u, v, 1) ^ lca(u, root, 1) ^ lca(v, root, 1)
  18. const int N = 1e5 + 5; 
  19. const int LOG = 17;  
  20.  
  21. int n, q;   
  22. vector<int> adj[N]; 
  23.  
  24. int up[LOG][N];   
  25. int tin[N], tout[N], timer;  
  26.  
  27. void reset() {
  28. 	for (int u = 1; u <= n; u++) {
  29. 		adj[u].clear();  
  30. 	}
  31. }
  32.  
  33. void dfs(int u, int p) {
  34. 	tin[u] = ++timer;   
  35. 	up[0][u] = p;   
  36. 	for (int i = 1; i < LOG; i++) {
  37. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  38. 	}
  39. 	for (int v : adj[u]) {
  40. 		if (v == p) continue; 
  41. 		dfs(v, u); 
  42. 	}
  43. 	tout[u] = timer;  
  44. }
  45.  
  46. bool isAncestor(int u, int v) {
  47. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]);
  48. }
  49.  
  50. // lca của 2 đỉnh u, v với gốc là 1
  51. int lca(int u, int v) {
  52. 	if (isAncestor(u, v)) return u;  
  53. 	if (isAncestor(v, u)) return v;  
  54. 	for (int i = LOG - 1; i >= 0; i--) {
  55. 		if (!isAncestor(up[i][u], v)) {
  56. 			u = up[i][u]; 
  57. 		}
  58. 	}
  59. 	return up[0][u]; 
  60. }
  61.  
  62. int main() {
  63. 	ios::sync_with_stdio(false); 
  64. 	cin.tie(nullptr); 	
  65. 	while (cin >> n) {
  66. 		if (n == 0) break; 
  67. 		reset();   
  68.  
  69. 		for (int i = 0; i < n - 1; i++) {
  70. 			int u, v; 
  71. 			cin >> u >> v; 
  72. 			adj[u].push_back(v);
  73. 			adj[v].push_back(u); 
  74. 		}
  75. 		cin >> q; 
  76.  
  77. 		int root = 1;  
  78. 		timer = 0;  
  79. 		dfs(1, 1); 
  80.  
  81. 		while (q--) {
  82. 			char type; cin >> type; 
  83. 			if (type == '!') {
  84. 				int nroot; cin >> nroot; 
  85. 				root = nroot; 
  86. 			}
  87. 			else {
  88. 				int u, v; 
  89. 				cin >> u >> v;  
  90. 				int lca_uv = lca(u, v) ^ lca(u, root) ^ lca(v, root); 
  91. 				cout << lca_uv << '\n'; 
  92. 			}
  93. 		}
  94. 	}
  95. }
Success #stdin #stdout 0.01s 13120KB
comments (?)
stdin
copy 
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
0
stdout
copy 
2
1
3
6
https://ideone.com/DgQwlx
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!