Advertisement
Josif_tepe

Untitled

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