Advertisement
Josif_tepe

Untitled

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