fork download
copy 
  1. /*
  2.  *  C. Terror in Terminus | SRBD Code Contest - 2024 (Round 1)
  3.  *  Author: Sohom Sahaun | @sohomsahaun | CF: sahaun
  4.  */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  10. using ll = long long;
  11.  
  12. struct BinaryLifting {
  13.   int n;
  14.   vector<int> depth, par, jump;
  15.  
  16.   BinaryLifting() {}
  17.   BinaryLifting(int n, int root = 0) : n(n) {
  18.     depth = vector<int>(n, 0);
  19.     par = vector<int>(n, -1);
  20.     jump = vector<int>(n, root);
  21.   }
  22.  
  23.   void set_root(int u, int root) {
  24.     jump[u] = root;
  25.   }
  26.  
  27.   void add_child(int u, int v) {
  28.     depth[v] = depth[u]+1;
  29.     par[v] = u;
  30.     jump[v] = u;
  31.     int x = jump[u];
  32.     if (depth[u]-depth[x] == depth[x]-depth[jump[x]]) {
  33.       jump[v] = jump[x];
  34.     }
  35.   }
  36.  
  37.   int get_parent(int u) {
  38.     return par[u];
  39.   }
  40.  
  41.   int get_depth(int u) {
  42.     return depth[u];
  43.   }
  44.  
  45.   int get_ancestor_at_depth(int u, int d) {
  46.     if (d < 0) return -1;
  47.     while (depth[u] > d) {
  48.       u = (depth[jump[u]] < d) ? par[u] : jump[u];
  49.     }
  50.     return u;
  51.   }
  52.  
  53.   int get_kth_ancestor(int u, int k) {
  54.     return get_ancestor_at_depth(u, depth[u]-k);
  55.   }
  56.  
  57.   int get_lca(int u, int v) {
  58.     if (depth[u] > depth[v]) swap(u, v);
  59.     v = get_ancestor_at_depth(v, depth[u]);
  60.     while (u != v) {
  61.       if (jump[u] == jump[v]) {
  62.         u = par[u];
  63.         v = par[v];
  64.       } else {
  65.         u = jump[u];
  66.         v = jump[v];
  67.       }
  68.     }
  69.     return u;
  70.   }
  71.  
  72.   int get_path_length(int u, int v) {
  73.     int x = get_lca(u, v);
  74.     return (depth[u]-depth[x] + depth[v]-depth[x]);
  75.   }
  76.  
  77.   bool is_in_path(int z, int u, int v) {
  78.     int x = get_lca(u, v);
  79.     if (get_lca(x, z) == x) {
  80.       if (get_lca(u, z) == z) return true;
  81.       if (get_lca(v, z) == z) return true;
  82.     }
  83.     return false;
  84.   }
  85. };
  86.  
  87. const int MX = 100005;
  88. vector<int> g[MX];
  89. BinaryLifting lift;
  90.  
  91. void lca_dfs(int u, int p = -1) {
  92.   for (int v : g[u]) {
  93.     if (v == p) continue;
  94.     lift.add_child(u, v);
  95.     lca_dfs(v, u);
  96.   }
  97. }
  98.  
  99. void init(int n) {
  100.   for (int i = 0; i <= n; ++i) {
  101.     g[i].clear();
  102.   }
  103.   lift = BinaryLifting(n);
  104. }
  105.  
  106. int main() {
  107.   FAST;
  108.  
  109.   int tc = 1, ti;
  110.   cin >> tc;
  111.  
  112.   for (ti = 1; ti <= tc; ++ti) {
  113.     int n, q, i, u, v, x, uv, ux, vx, req, z;
  114.     cin >> n;
  115.     init(n);
  116.  
  117.     for (i = 1; i < n; ++i) {
  118.       cin >> u >> v;
  119.       --u; --v;
  120.       g[u].push_back(v);
  121.       g[v].push_back(u);
  122.     }
  123.     lca_dfs(0);
  124.  
  125.     cin >> q; while (q--) {
  126.       cin >> u >> v;
  127.       --u; --v;
  128.  
  129.       x = lift.get_lca(u, v);
  130.       uv = lift.get_path_length(u, v);
  131.       ux = lift.get_path_length(u, x);
  132.       vx = lift.get_path_length(v, x);
  133.  
  134.       req = uv/2;
  135.  
  136.       z = -1;
  137.       if (ux >= req) {
  138.         z = lift.get_kth_ancestor(u, req);
  139.       } else {
  140.         z = lift.get_kth_ancestor(v, vx - (req - ux));
  141.       }
  142.  
  143.       cout << z+1 << "\n";
  144.     }
  145.  
  146.   }
  147.  
  148.   return 0;
  149. }
Success #stdin #stdout 0.01s 5832KB
comments (?)
stdin
copy 
2
3
1 2
3 1
4
1 1
1 3
2 1
2 3
8
8 2
5 1
8 3
5 6
4 2
7 2
7 6
5
2 5
5 1
6 4
8 1
8 2
stdout
copy 
1
1
2
1
7
5
7
7
8
https://ideone.com/F4iHBv
language:
C++14 (gcc 8.3)
created:
4 days 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!