# Untitled

Sep 4th, 2020
39
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define int long long
3. #define pb push_back
4. #define endl "\n"
5. using namespace std;
6.
7. const int N = 3e5 + 10;
8. vector<int> gr[N], tin(N), tout(N), dep(N);
9. int up[N][20], timer;
10.
11. void calc(int v, int pr = 1) {
12. up[v][0] = pr;
13. for(int i = 1; i < 20; i++) {
14. up[v][i] = up[up[v][i - 1]][i - 1];
15. }
16. tin[v] = timer++;
17. for(auto it: gr[v]) {
18. if(it != pr) {
19. dep[it] = dep[v] + 1;
20. calc(it, v);
21. }
22. }
23. tout[v] = timer++;
24. }
25.
26. bool upper(int a, int b) {
27. return tin[a] <= tin[b] && tout[a] >= tout[b];
28. }
29.
30. int lca(int a, int b) {
31. if(upper(a, b)) return a;
32. if(upper(b, a)) return b;
33. for(int i = 19; i >= 0; i--) {
34. if(!upper(up[a][i], b)) {
35. a = up[a][i];
36. }
37. }
38. return up[a][0];
39. }
40.
41. int dist(int a, int b) {
42. return dep[a] + dep[b] - 2 * dep[lca(a, b)];
43. }
44.
45. int getpar(int v, int l) {
46. for(int i = 19; i >= 0; i--) {
47. if((1 << (i)) <= l) {
48. l -= (1 << (i));
49. v = up[v][i];
50. }
51. }
52. return v;
53. }
54.
55. main() {
56. ios_base::sync_with_stdio(0);
57. cin.tie(0);
58. cout.tie(0);
59. int n;
60. cin >> n;
61. for(int i = 1; i < n; i++) {
62. int l, r;
63. cin >> l >> r;
64. gr[l].pb(r);
65. gr[r].pb(l);
66. }
67. calc(1);
68. int q;
69. cin >> q;
70.
71. while(q--) {
72. int l, r;
73. cin >> l >> r;
74. int e;
75. cin >> e;
76. if(dist(l, r) <= e) {
77. cout << r << endl;
78. } else {
79. int mid = lca(l, r);
80. if(e < dist(l, mid)) {
81. cout << getpar(l, e) << endl;
82. continue;
83. }
84. if(e == dist(l, mid)) {
85. cout << mid << endl;
86. continue;
87. }
88. e -= dist(l, mid);
89. e = dist(mid, r) - e;
90. cout << getpar(r, e) << endl;
91. }
92. }
93. }
RAW Paste Data