fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class LCASparseTable{
  6. public:
  7.    long long len;
  8.    vector<vector<int> > up;
  9.    vector<int> tin;
  10.    vector<int> tout;
  11.    int time;
  12.    int n;
  13.    vector<vector<int> > tree;
  14.  
  15.    LCASparseTable(int n){
  16.       this -> n = n;
  17.       tree.resize(n + 5);
  18.       up.resize(25);
  19.       for(int i = 0; i < 25; ++i){
  20.          up[i].resize(n + 5);
  21.       }
  22.       tin.resize(n + 5);
  23.       tout.resize(n + 5);
  24.       len = 1;
  25.       while((1ll << len) <= n){
  26.          ++len;
  27.       }
  28.    }
  29.  
  30.    void dfs(int u, int p){
  31.       tin[u] = time++;
  32.       up[0][u] = p;
  33.       for(int i = 1; i < len; ++i){
  34.          up[i][u] = up[i - 1][up[i - 1][u]];
  35.       }
  36.       for(auto v : tree[u]){
  37.          if(v != p){
  38.             dfs(v, u);
  39.          }
  40.       }
  41.       tout[u] = time++;
  42.    }
  43.  
  44.    void build(int root){
  45.       dfs(root, root);
  46.    }
  47.  
  48.    bool isParent(int parent, int child){
  49.       return tin[parent] <= tin[child] && tout[child] <= tout[parent];
  50.    }
  51.  
  52.    int lca(int a, int b){
  53.       if(isParent(a, b)) return a;
  54.       if(isParent(b, a)) return b;
  55.       for(int i = len - 1; i >= 0; --i){
  56.          if(!isParent(up[i][a], b)){
  57.             a = up[i][a];
  58.          }
  59.       }
  60.       return up[0][a];
  61.    }
  62. };
  63.  
  64. int main(){
  65.    int n;
  66.    cin >> n;
  67.    LCASparseTable lcast(n);
  68.    int x, y;
  69.    for(int i = 0; i < n - 1; ++i){
  70.       scanf("%d%d", &x, &y);
  71.       lcast.tree[x].push_back(y);
  72.       lcast.tree[y].push_back(x);
  73.    }
  74.    lcast.build(1);
  75.    for(int i = 1; i <= n; ++i){
  76.       for(int j = 1; j <= n; ++j){
  77.          printf("%d-%d: %d\n", i, j, lcast.lca(i, j));
  78.       }
  79.    }
  80.    return 0;
  81. }
  82.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
9
1 2
1 3
3 4
3 5
2 6
6 7
5 8
9 5
---------
Given tree:

    1
   / \
  2   3
 /   / \
6   4   5
 \     / \
  7   8   9
stdout
copy 
1-1: 1
1-2: 1
1-3: 1
1-4: 1
1-5: 1
1-6: 1
1-7: 1
1-8: 1
1-9: 1
2-1: 1
2-2: 2
2-3: 1
2-4: 1
2-5: 1
2-6: 2
2-7: 2
2-8: 1
2-9: 1
3-1: 1
3-2: 1
3-3: 3
3-4: 3
3-5: 3
3-6: 1
3-7: 1
3-8: 3
3-9: 3
4-1: 1
4-2: 1
4-3: 3
4-4: 4
4-5: 3
4-6: 1
4-7: 1
4-8: 3
4-9: 3
5-1: 1
5-2: 1
5-3: 3
5-4: 3
5-5: 5
5-6: 1
5-7: 1
5-8: 5
5-9: 5
6-1: 1
6-2: 2
6-3: 1
6-4: 1
6-5: 1
6-6: 6
6-7: 6
6-8: 1
6-9: 1
7-1: 1
7-2: 2
7-3: 1
7-4: 1
7-5: 1
7-6: 6
7-7: 7
7-8: 1
7-9: 1
8-1: 1
8-2: 1
8-3: 3
8-4: 3
8-5: 5
8-6: 1
8-7: 1
8-8: 8
8-9: 5
9-1: 1
9-2: 1
9-3: 3
9-4: 3
9-5: 5
9-6: 1
9-7: 1
9-8: 5
9-9: 9
https://ideone.com/mk3ocX
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!