fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int maxN = 7e4;
  5.  
  6. int N, Q, h[maxN] = {0}, up[maxN][20];
  7. vector<int> edge[maxN];
  8. //
  9. void DFS (int u)
  10. {
  11.     for (int v : edge[u])
  12.     {
  13.         if (v == up[u][0])
  14.             continue;
  15.         h[v] = h[u] + 1;
  16.         up[v][0] = u;
  17.         for (int i = 1; i < 20; ++i)
  18.             up[v][i] = up[up[v][i - 1]][i - 1];
  19.         DFS(v);
  20.     }
  21. }
  22. int LCA (int u, int v)
  23. {
  24.     if (h[u] != h[v])
  25.     {
  26.         if (h[u] < h[v])
  27.             swap(u, v);
  28.         for (int k = h[u] - h[v], i = 0; 1 << i <= k; ++i)
  29.             if (k >> i & 1)
  30.                 u = up[u][i];
  31.     }
  32.     if (u == v)
  33.         return u;
  34.     for (int i = __lg(h[u]); i >= 0; --i)
  35.         if (up[u][i] != up[v][i])
  36.             u = up[u][i], v = up[v][i];
  37.     return up[v][0];
  38. }
  39. //
  40. struct Segment_Tree
  41. {
  42.     int node[maxN << 1];
  43.     //
  44.     void build (void)
  45.     {
  46.         for (int i = 0; i < N; ++i)
  47.             node[i + N] = i;
  48.         for (int id = N - 1; id > 0; --id)
  49.             node[id] = LCA(node[id << 1], node[id << 1 | 1]);
  50.     }
  51.     int query (int l, int r)
  52.     {
  53.         int res = l;
  54.         //
  55.         for (l += N, r += N; l < r; l >>= 1, r >>= 1)
  56.         {
  57.             if (l & 1)
  58.                 res = LCA(res, node[l++]);
  59.             if (r & 1)
  60.                 res = LCA(res, node[--r]);
  61.         }
  62.         return res + 1;
  63.     }
  64. } ST;
  65. //
  66. struct process
  67. {
  68.     void input (void)
  69.     {
  70.         int u, v;
  71.         //
  72.         cin >> N >> Q;
  73.         for (int i = 1; i < N; ++i)
  74.             cin >> u >> v,
  75.             edge[--u].emplace_back(--v),
  76.             edge[v].emplace_back(u);
  77.     }
  78.     void solve (void)
  79.     {
  80.         DFS(0);
  81.         ST.build();
  82.     }
  83.     void output (void)
  84.     {
  85.         for (int u, v; Q--;)
  86.             cin >> u >> v,
  87.             cout << ST.query(--u, v) << '\n';
  88.     }
  89.     //
  90.     process (void)
  91.     {
  92.         input(), solve(), output();
  93.     }
  94. };
  95. //
  96. signed main (void)
  97. {
  98.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  99.     process();
  100. }
  101.  
Success #stdin #stdout 0.01s 6560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/V2YgPC
https://o...content-available-to-author-only...i.info/problem/votree
language:
C++14 (gcc 8.3)
created:
4 hours 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!