Advertisement
willy108

sqrt lca

Mar 17th, 2021
682
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. const int R = 330, MX = 1e5 +10;
  4. vector<int> adj[MX];
  5. int dep[MX], par[MX], super[MX], n, q;
  6.  
  7. void dfs(int u, int p, int d){
  8.     par[u] = p;
  9.     dep[u] = d;
  10.     for(int v : adj[u]){
  11.         if(v != p) dfs(v, u, d + 1);
  12.     }
  13. }
  14. //note this lca implementation is in 1-based indexing
  15. //so node 0 is "parent" of the root
  16. void precomp(){
  17.     for(int i = 1; i<=n; i++){
  18.         super[i] = i;
  19.         for(int j = 0; j<R && super[i] != 0; j++) super[i] = par[super[i]];  
  20.     }
  21. }
  22.  
  23. int k_up(int u, int k){
  24.    while(k >= R) k = k/R, u = super[u];
  25.    for(int i = 0; i<k; i++) u = par[u];
  26.    return 0;
  27. }
  28.  
  29. int lca(int u, int v){
  30.   if(dep[u] < dep[v]) swap(u, v);
  31.   u = k_up(u, dep[u] - dep[v]);
  32.   while(super[u] != super[v]){
  33.     u = super[u], v = super[v];
  34.   }
  35.   while(u != v){
  36.     u = par[u], v = par[v];
  37.   }
  38.   return u;
  39. }
  40.  
  41. int main(){
  42.     cin >> n;
  43.     for(int i = 1; i<n; i++){
  44.         int a, b; cin >> a >> b;
  45.         adj[a].pb(b);
  46.         adj[b].pb(a);
  47.     }
  48.     dfs(1, 0, 0);
  49.     precomp();
  50.     while(q--){
  51.         int a, b; cin >> a >> b;
  52.         cout << lca(a, b) << '\n';
  53.     }
  54.     return 0;
  55. }
  56.  
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement