fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define TEST int t;cin >> t;while (t--)
  6. #define fastio ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  7. #define ll long long
  8. #define ld long double
  9.  
  10. template<typename treeType = ll, typename graphType = ll>
  11. class LCA {
  12. public:
  13.     LCA(
  14.         ll n = 0,
  15.         const vector<vector<treeType> > &G = {},
  16.         ll root = 1
  17.     ) : N(n), LOG(0), ROOT(root), adj(G) {
  18.         while ((1 << LOG) <= N) LOG++;
  19.         anc.assign(N + 5, vector<ll>(LOG));
  20.         depth.assign(N + 5, 0);
  21.         dfs(ROOT);
  22.     }
  23.  
  24.     ll kth_ancestor(ll u, ll k) const {
  25.         if (depth[u] < k) return -1;
  26.         for (ll bit = 0; bit < LOG; bit++)
  27.             if (k & (1 << bit))
  28.                 u = anc[u][bit];
  29.         return u;
  30.     }
  31.  
  32.     ll get_lca(ll u, ll v) const {
  33.         if (depth[u] < depth[v]) swap(u, v);
  34.  
  35.         u = kth_ancestor(u, depth[u] - depth[v]);
  36.         if (u == v) return u;
  37.  
  38.         for (ll bit = LOG - 1; bit >= 0; bit--)
  39.             if (anc[u][bit] != anc[v][bit])
  40.                 u = anc[u][bit], v = anc[v][bit];
  41.  
  42.         return anc[u][0];
  43.     }
  44.  
  45.     // treeType query(ll u, ll v) const {
  46.     //     ll lca = get_lca(u, v);
  47.     //     return operation(get_cost(u, depth[u] - depth[lca]), get_cost(v, depth[v] - depth[lca]));
  48.     // }
  49.  
  50. private:
  51.     ll N, LOG, ROOT;
  52.     const vector<vector<treeType> > &adj;
  53.     vector<vector<ll> > anc;
  54.     // vector < vector < treeType > > cost;
  55.     vector<ll> depth;
  56.     // function < treeType(treeType, treeType) > operation;
  57.     // treeType neutral;
  58.  
  59.     void dfs(ll u, ll p = 0) {
  60.         for (auto &v: adj[u]) {
  61.             if (v == p) continue;
  62.             depth[v] = depth[u] + 1;
  63.             anc[v][0] = u;
  64.             for (ll bit = 1; bit < LOG; bit++) {
  65.                 anc[v][bit] = anc[anc[v][bit - 1]][bit - 1];
  66.             }
  67.             dfs(v, u);
  68.         }
  69.     }
  70.  
  71.     // treeType get_cost(ll u, ll dist) const {
  72.     //     if(depth[u] < dist) return neutral;
  73.     //     treeType ret = neutral;
  74.     //     for(ll bit = 0; bit < LOG; bit++){
  75.     //         if(dist & (1 << bit)){
  76.     //             ret = operation(ret, cost[u][bit]);
  77.     //             u = anc[u][bit];
  78.     //         }
  79.     //     }
  80.     //     return ret;
  81.     // }
  82. };
  83.  
  84. void solve(ll tc = 1) {
  85.     ll n, q;
  86.     cin >> n;
  87.     vector<vector<ll> > G(n + 2);
  88.  
  89.     for (ll i = 1; i < n; i++) {
  90.         ll u, v;
  91.         cin >> u >> v;
  92.         G[u].push_back(v);
  93.         G[v].push_back(u);
  94.     }
  95.     LCA<ll> g(n, G, 1);
  96.     cin >> q;
  97.     while (q--) {
  98.         ll r, u, v;
  99.         cin >> r >> u >> v;
  100.         if (r==1) cout << g.get_lca(u, v) << endl;
  101.         else cout << max( g.get_lca(u,r) , g.get_lca(v,r) ) << endl ;
  102.     }
  103. }
  104.  
  105.  
  106. int main() {
  107.     fastio
  108.     // TEST
  109.     solve();
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B7UJRS
language:
C++14 (gcc 8.3)
created:
5 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!