tumaryui

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