liartie

Untitled

Dec 11th, 2020
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector <vector <int> > g;
  7. vector <int> d;
  8. vector <int> first;
  9. vector <int> euler;
  10.  
  11. void dfs(int v, int p = -1){
  12.     if(p == -1){
  13.         d[v] = 0;
  14.     }
  15.     else{
  16.         d[v] = d[p] + 1;
  17.     }
  18.     first[v] = euler.size();
  19.     euler.push_back(v);
  20.     for(int u : g[v]){
  21.         if(u != p){
  22.             dfs(u, v);
  23.             euler.push_back(v);
  24.         }
  25.     }
  26. }
  27.  
  28. vector <vector <int> > sparse;
  29. vector <int> logs;
  30.  
  31. inline int Min(int u, int v){
  32.     return d[u] < d[v] ? u : v;
  33. }
  34.  
  35. int ask(int l, int r){
  36.     int level = logs[l - r + 1];
  37.     return Min(sparse[level][l], sparse[level][r - (1 << level) + 1]);
  38. }
  39.  
  40. int lca(int u, int v){
  41.     u = first[u];
  42.     v = first[v];
  43.     if(u > v){
  44.         swap(u, v);
  45.     }
  46.     return ask(u, v);
  47. }
  48.  
  49. int main(){
  50.     int n, q;
  51.     cin>>n;
  52.     g.resize(n);
  53.     d.resize(n);
  54.     first.resize(n);
  55.     for(int i = 0; i < n - 1; i++){
  56.         int a, b;
  57.         cin>>a>>b;
  58.         a--;
  59.         b--;
  60.         g[a].push_back(b);
  61.         g[b].push_back(a);
  62.     }
  63.     dfs(0);
  64.     int l = euler.size();
  65.     logs.resize(l + 1);
  66.     logs[1] = 0;
  67.     for(int i = 2; i <= l; i++){
  68.         logs[i] = logs[i / 2] + 1;
  69.     }
  70.     sparse.resize(logs[l] + 1, vector <int> (l));
  71.     for(int i = 0; i < l; i++){
  72.         sparse[0][i] = euler[i];
  73.     }
  74.     for(int level = 1; (1 << level) <= l; level++){
  75.         for(int i = 0; i + (1 << level) <= l; i++){
  76.             sparse[level][i] = Min(sparse[level - 1][i], sparse[level - 1][i + (1 << level - 1)]);
  77.         }
  78.     }
  79.     cin>>q;
  80.     while(q--){
  81.         int a, b;
  82.         cin>>a>>b;
  83.         a--;
  84.         b--;
  85.        
  86.     }
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment