fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define BIT(i) (1LL << i)
  5. typedef long long ll;
  6. const int MAXN = 1e5 + 7;
  7. int par[MAXN][27], h[MAXN], n, k;
  8. int root = 1;
  9. vector <int> a[MAXN];
  10. void dfs(int u){
  11.     for(int i = 1; i <= 20; i++) par[u][i] = par[par[u][i - 1]][i - 1];
  12.     for(auto v : a[u]){
  13.         if(v != par[u][0]){
  14.             par[v][0] = u;
  15.             h[v] = h[u] + 1;
  16.             dfs(v);
  17.         }
  18.     }
  19. }
  20.  
  21. int lca(int u, int v){
  22.     if(h[u] < h[v]) swap(u, v);
  23.     int x = h[u] - h[v];
  24.     for(int i = 20; i >= 0; i--){
  25.         if(x >= BIT(i)){
  26.             x -= BIT(i);
  27.             u = par[u][i];
  28.         }
  29.     }
  30.     if(u == v)return u;
  31.     int h_max = __lg(h[u]);
  32.     for(int i = h_max; i >= 0; i--){
  33.         if(par[u][i] != par[v][i]){
  34.             u = par[u][i];
  35.             v = par[v][i];
  36.         }
  37.     }
  38.     return par[v][0];
  39. }
  40.  
  41.  
  42. int main(){
  43.     ios_base::sync_with_stdio(0);
  44.     cout.tie(0);
  45.     cin.tie(0);
  46.     cin >> n;
  47.     for(int i = 1; i <= n - 1; i++){
  48.         int  x, y;
  49.         cin >> x >> y;
  50.         a[x].pb(y);
  51.         a[y].pb(x);
  52.     }
  53.     dfs(1);
  54.     cin >> k;
  55.     while(k--){
  56.         int u, v;
  57.         char q;
  58.         cin >> q;
  59.         if(q == '!')cin >> root;
  60.         else{
  61.             cin >> u >> v;
  62.             int uv = lca(u, v);
  63.             int ur = lca(u, root);
  64.             int vr = lca(v, root);
  65.             if(ur == vr) cout << uv << endl; 
  66.             else if(h[vr] > h[ur]) cout << vr << endl;
  67.             else cout << ur << endl;
  68.         }
  69.     }
  70. }
  71.  
Success #stdin #stdout 0.01s 7760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iIJ47M
language:
C++14 (gcc 8.3)
created:
19 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!