fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int maxN = 1e5 + 5;
  5. //
  6. int N, M, root, h[maxN], up[maxN][20];
  7. vector<int> edge[maxN];
  8. //
  9. void reset (void)
  10. {
  11.     root = 1;
  12.     for (int i = 1; i <= N; ++i)
  13.         edge[i].clear();
  14. }
  15. void DFS (int u)
  16. {
  17.     for (int v : edge[u])
  18.     {
  19.         if (v == up[u][0])
  20.             continue;
  21.         h[v] = h[u] + 1;
  22.         up[v][0] = u;
  23.         for (int j = 1; j < 20; ++j)
  24.             up[v][j] = up[up[v][j - 1]][j - 1];
  25.         DFS(v);
  26.     }
  27. }
  28. int LCA (int u, int v)
  29. {
  30.     if (h[u] != h[v])
  31.     {
  32.         if (h[u] < h[v])
  33.             swap(u, v);
  34.         for (int k = h[u] - h[v], i = 0; (1 << i) <= k; ++i)
  35.             if (k >> i & 1)
  36.                 u = up[u][i];
  37.     }
  38.     if (u == v)
  39.         return u;
  40.     for (int k = __lg(h[v]); k >= 0; --k)
  41.         if (up[u][k] != up[v][k])
  42.             u = up[u][k], v = up[v][k];
  43.     return up[v][0];
  44. }
  45. int query (int u, int v)
  46. {
  47.     int a = LCA(u, v), b = LCA(u, root), c = LCA(v, root);
  48.     //
  49.     if (b == c)
  50.         return a;
  51.     return c == a ? b : c;
  52. }
  53. //
  54. void process (void)
  55. {
  56.     int M, u, v;
  57.     char type;
  58.     //
  59.     while (cin >> N)
  60.     {
  61.         if (N == 0)
  62.             break;
  63.         reset();
  64.         while (--N)
  65.             cin >> u >> v,
  66.             edge[u].emplace_back(v), edge[v].emplace_back(u);
  67.         DFS(1);
  68.         for (cin >> M; M--;)
  69.         {
  70.             cin >> type;
  71.             if (type == '!')
  72.                 cin >> root;
  73.             else
  74.                 cin >> u >> v,
  75.                 cout << query(u, v) << '\n';
  76.         }
  77.     }
  78. }
  79. //
  80. signed main (void)
  81. {
  82.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  83.     process();
  84. }
  85.  
Success #stdin #stdout 0.01s 6588KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/n5dye7
language:
C++14 (gcc 8.3)
created:
3 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!