Advertisement
Josif_tepe

Untitled

Jul 15th, 2023
712
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. const int maxn = 1e6 + 10;
  6. vector<int> graph[maxn];
  7. int in_time[maxn], out_time[maxn];
  8. int up_node[maxn][25];
  9.  
  10. int timer, LOG, n;
  11. void dfs(int node, int parent) {
  12.     in_time[node] = ++timer;
  13.     up_node[node][0] = parent;
  14.    
  15.     for(int i = 1; i <= LOG; i++) {
  16.         up_node[node][i] = up_node[ up_node[node][i - 1] ][i - 1];
  17.     }
  18.    
  19.     for(int i = 0; i < (int) graph[node].size(); i++) {
  20.         int neighbour = graph[node][i];
  21.         if(parent != neighbour) {
  22.             dfs(neighbour, node);
  23.         }
  24.     }
  25.     out_time[node] = ++timer;
  26. }
  27. bool is_ancestor(int A, int B) {
  28.     return in_time[A] <= in_time[B] and out_time[A] >= out_time[B];
  29. }
  30. int LCA(int A, int B) {
  31.     if(is_ancestor(A, B)) {
  32.         return A;
  33.     }
  34.     if(is_ancestor(B, A)) {
  35.         return B;
  36.     }
  37.     for(int i = LOG; i >= 0; i--) {
  38.         if(!is_ancestor(up_node[A][i], B)) {
  39.             A = up_node[A][i];
  40.         }
  41.     }
  42.     return up_node[A][0];
  43. }
  44. void preprocess() {
  45.     timer = 0;
  46.     LOG = 0;
  47.     while((1 << LOG) <= n) {
  48.         LOG++;
  49.     }
  50.     dfs(0, -1);
  51. }
  52. int main() {
  53.     ios_base::sync_with_stdio(false);
  54.    
  55.     cin >> n;
  56.    
  57.     for(int i = 1; i < n; i++) {
  58.         int a, b;
  59.         cin >> a >> b;
  60.         a--; b--;
  61.         graph[a].push_back(b);
  62.         graph[b].push_back(a);
  63.     }
  64.     preprocess();
  65.    
  66.     int q;
  67.     cin >> q;
  68.     for(int i = 0; i < q; i++) {
  69.         int a, b;
  70.         cin >> a >> b;
  71.         a--; b--;
  72.         cout << LCA(a, b) << endl;
  73.     }
  74.     return 0;
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement