Advertisement
ashibh

Untitled

Jun 19th, 2023
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | Source Code | 0 0
  1. //                                                     (┬┬﹏┬┬)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define lli long long int
  5. #define Endl endl;
  6. #define yy cout << "YES" << endl
  7. #define nn cout << "NO" << endl
  8. long long int inf = 1000000007;
  9. #define all(x) x.begin(), x.end()
  10. const char nl = '\n';
  11.  
  12.  
  13. void sot(vector<lli>&v) {
  14.     sort(all(v));
  15. }
  16. void ipv(vector<lli>&v, lli n) {
  17.     for (lli i = 0; i < n; i++)cin >> v[i];
  18. }
  19. void opv(vector<lli>&v, lli n) {
  20.     for (lli i = 0; i < n; i++)cout << v[i] << " ";
  21. }
  22. void ipvm(vector<lli>&v, lli n, map<lli, lli>&mp) {
  23.     for (lli i = 0; i < n; i++)mp[v[i]]++;
  24. }
  25. void opvm(map<lli, lli>mp) {
  26.     for (auto it : mp)cout << it.first << " " << it.second << " ";
  27.     cout << nl;
  28. }
  29. void ips(string s) {
  30.     cin >> s;
  31. }
  32. lli gcd(lli a, lli b)
  33. {
  34.     if (a == 0)
  35.         return b;
  36.     return gcd(b % a, a);
  37. }
  38.  
  39. // Function to return LCM of two numbers
  40. lli lcm(lli a, lli b)
  41. {
  42.     return (a / gcd(a, b)) * b;
  43. }
  44.  
  45.  
  46. bool isPrm(lli n)
  47. {
  48.  
  49.     if (n <= 1)
  50.         return false;
  51.     for (lli i = 2; i <= sqrt(n); i++)
  52.         if (n % i == 0)
  53.             return false;
  54.  
  55.     return true;
  56. }
  57.  
  58.  
  59. //
  60. //
  61. //
  62. //
  63. //
  64. // -----------------------graph-LCA-Binary_lifting------------------------------------------------------------------------------
  65. const lli N = 3e5 + 10;
  66. const int Log = 18;
  67.  
  68. vector<lli>g[N];
  69. bool vis[N];
  70. // vector<vector<lli>>up;
  71. lli up[N][Log];
  72. vector<lli>parent(N);
  73. vector<lli>depth(N);
  74. // ---------------------list dfs-----------------------------------------------------------------------------
  75. void dfs(lli v, lli par) {
  76.     vis[v] = 1;
  77.     depth[v] = depth[par] + 1;
  78.     up[v][0] = par;
  79.     // cout << v << " " << par << nl;
  80.  
  81.  
  82.     for (int j = 1; j < Log; j++) {
  83.         up[v][j] = up[ up[v][j - 1] ][j - 1];
  84.     }
  85.  
  86.     for (lli ch : g[v]) {
  87.         if (vis[ch] == 0)
  88.             dfs(ch, v);
  89.     }
  90. }
  91.  
  92. lli lca(lli a, lli b) {
  93.     if (depth[a] < depth[b]) {
  94.         swap(a, b);
  95.     }
  96.     lli k = depth[a] - depth[b];
  97.     for (int i = Log - 1; i >= 0 ; --i)
  98.     {
  99.         if (k & (1 << i)) {
  100.             a = up[a][i];
  101.         }
  102.     }
  103.     if (a == b)return a;
  104.     for (int i = Log - 1; i >= 0 ; --i)
  105.     {
  106.         if (up[a][i] != up[b][i]) {
  107.             a = up[a][i];
  108.             b = up[b][i];
  109.  
  110.         }
  111.     }
  112.     return up[a][0];
  113.  
  114. }
  115. lli kthAncestor(lli v, lli k) {
  116.     for (int i = Log - 1; i >= 0 ; --i)
  117.     {
  118.         if (k & (1 << i)) {
  119.             v = up[v][i];
  120.         }
  121.     }
  122.     return v;
  123. }
  124.  
  125. void cf()
  126. {
  127.     lli f = 0, e = 0, o = 0, p, q, r, t;
  128.     lli n;
  129.     cin >> n;
  130.     for (int i = 0; i < n - 1; ++i)
  131.     {
  132.         lli u, v;
  133.         cin >> u >> v;
  134.         g[v].push_back(u);
  135.         g[u].push_back(v);
  136.  
  137.     }
  138.     cin >> q;
  139.     dfs(1, 1);
  140.     while (q--) {
  141.         lli x, y, e;
  142.         cin >> x >> y >> e;
  143.         p = lca(x, y);
  144.         // cout << p << nl;
  145.         lli dis = depth[x] + depth[y] - 2 * depth[p];
  146.         if (dis > e) {
  147.             lli d1 = depth[x] - depth[p];
  148.             if (e > d1) {
  149.                 cout << kthAncestor(y, e - d1) << nl;
  150.             } else {
  151.                 cout << kthAncestor(x, e) << nl;
  152.             }
  153.  
  154.  
  155.         } else {
  156.             cout << y << nl;
  157.         }
  158.     }
  159.  
  160.  
  161.  
  162. }
  163.  
  164.  
  165. int main()
  166. {
  167.     ios_base::sync_with_stdio(0);
  168.     cin.tie(0);
  169.     cout.tie(0);
  170. #ifndef ONLINE_JUDGE
  171.     freopen("input.txt", "r", stdin);
  172.     freopen("output.txt", "w", stdout);
  173. #endif
  174.     lli t = 1;
  175.     // cin >> t;
  176.     while (t--)
  177.     {
  178.         cf();
  179.     }
  180. }
  181. //-----------------------------------comments----------------------------------------------------------------------------
  182. //lb(x)= ele eq or greater then x (first occ)
  183. //ub(x)= ele greater then x
  184.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement