fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define file(name) if (fopen(name".INP", "r")){freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);}
  5.  
  6. const int maxn = 1e6 + 7;
  7. const int LOG = log2(maxn);
  8.  
  9. int n, q, st[LOG + 1][maxn], f[LOG + 1][maxn], h[maxn];
  10. std::vector<int> adj[maxn];
  11. bool visited[maxn];
  12.  
  13. void dfs(){
  14. 	memset(visited, false, maxn);
  15. 	queue <int> q;
  16. 	q.push(1);
  17. 	h[1] = 1;
  18. 	while (not q.empty()){
  19. 		int u = q.front();
  20. 		q.pop();
  21. 		if (not visited[u]){
  22. 			visited[u] = true;
  23. 			for (auto &v: adj[u]){
  24. 				if (v != st[0][u]){
  25. 					st[0][v] = u;
  26. 					h[v] = h[u] + 1;
  27. 					for (int i = 1; i <= LOG; i++)
  28. 						st[i][v] = st[i-1][st[i-1][v]];
  29. 					q.push(v);
  30. 				}
  31. 			}
  32. 		}
  33. 	}
  34. }
  35.  
  36. int lca(int u, int v){
  37. 	if (h[u] < h[v]) swap(u, v);
  38. 	int k = h[u] - h[v];
  39. 	for (int i = LOG; i >= 0; i--)
  40. 		if (k >> i & 1) u = st[i][u];
  41. 	if (u == v) return u;
  42. 	for (int i = LOG; i >= 0; i--)
  43. 		if (st[i][u] != st[i][v]) u = st[i][u], v = st[i][v];
  44. 	return st[0][u];
  45. }
  46.  
  47. int get(int l, int r){
  48. 	int k = log2(r - l + 1);
  49. 	return lca(f[k][l], f[k][r - (1 << k) + 1]);
  50. }
  51.  
  52. void solution(){
  53.  
  54. 	cin >> n;
  55. 	for (int i = 2; i <= n; i++){
  56. 		int u, v; cin >> u >> v;
  57. 		adj[u].emplace_back(v);
  58. 		adj[v].emplace_back(u);
  59. 	}
  60. 	dfs();
  61. 	for (int i = 1; i <= n; i++) f[0][i] = i;
  62. 	for (int i = 1; (1 << i) <= n; i++)
  63. 		for (int j = 1; j <= n - (1 << i) + 1; j++)
  64. 			f[i][j] = lca(f[i-1][j], f[i-1][j + (1 << (i-1))]);
  65. 	cin >> q;
  66. 	while (q --> 0){
  67. 		int l, r; cin >> l >> r;
  68. 		cout << get(l, r) << "\n";
  69. 	}
  70.  
  71. }
  72.  
  73. signed main(){
  74. 	ios_base::sync_with_stdio(0);
  75. 	cin.tie(0); cout.tie(0);
  76.  
  77. 	file("TEST");
  78.  
  79. 	solution();
  80.  
  81. 	return 0;
  82. }
Success #stdin #stdout 0.02s 27992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/p3zVXA
language:
C++ (gcc 8.3)
created:
1 year 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!