fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int int64_t
  5. #define endl '\n'
  6. #define vi vector<int>
  7. #define vvi vector<vi>
  8. #define each(a) for(auto& e: a)
  9. #define rep(n, i) for(int i = 0; i < n; i++)
  10.  
  11. void solve() {
  12. 	int n;
  13. 	cin >> n;
  14. 	vvi G(n), dp(n, vi(20));
  15. 	rep(n - 1, _) {
  16. 		int u, v;
  17. 		cin >> u >> v;
  18. 		u--; v--;
  19. 		G[u].push_back(v);
  20. 		G[v].push_back(u);
  21. 	}
  22. 	vi tin(n), tout(n);
  23. 	int t = 0;
  24. 	function<void(int, int)> dfs = [&](int i, int p) {
  25. 		if(p != -1) {
  26. 			dp[i][0] = p;
  27. 			for(int j = 1; j < 20; j++) {
  28. 				dp[i][j] = dp[dp[i][j - 1]][j - 1];
  29. 			}
  30. 		}
  31. 		tin[i] = t++;
  32. 		each(G[i]) {
  33. 			if(e != p) dfs(e, i);
  34. 		}
  35. 		tout[i] = t++;
  36. 	};
  37. 	dfs(0, -1);
  38. 	auto is_ancestor = [&](int u, int v) {
  39. 		return tin[u] <= tin[v] && tout[u] >= tout[v];
  40. 	};
  41. 	auto lca = [&](int u, int v) {
  42. 		if(is_ancestor(u, v)) return u;
  43. 		if(is_ancestor(v, u)) return v;
  44. 		for(int j = 19; j >= 0; j--) {
  45. 			if(!is_ancestor(dp[u][j], v)) u = dp[u][j];
  46. 		}
  47. 		return dp[u][0];
  48. 	};
  49. 	auto get_descendant = [&](int u, int v) {
  50. 		if(is_ancestor(u, v)) return v;
  51. 		return u;
  52. 	};
  53. 	int q;
  54. 	cin >> q;
  55. 	while(q--) {
  56. 		int u, v, w;
  57. 		cin >> u >> v >> w;
  58. 		u--; v--; w--;
  59. 		int ans = lca(u, v);
  60. 		ans = get_descendant(ans, lca(u, w));
  61. 		ans = get_descendant(ans, lca(v, w));
  62. 		cout << ans + 1 << endl;
  63. 	}
  64. }
  65.  
  66. int32_t main() {
  67. 	int t = 1;
  68. 	cin >> t;
  69. 	while(t--) {
  70. 		solve();
  71. 		cout << endl;
  72. 	}
  73. }
Success #stdin #stdout 0.01s 5528KB
comments (?)
stdin
copy 
1
6
1 2
1 3
1 4
3 5
3 6
4
2 5 6
5 2 6
2 5 1
2 5 4
stdout
copy 
3
3
1
1
https://ideone.com/r4bB3U
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!