fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mx=2e5+5;
  4. int n, q;
  5. vector<int> adj[mx];
  6. int up[mx][20], dep[mx]; 
  7.  
  8. // DFS một lần để tính độ sâu và xây bảng up
  9. void dfs(int u, int p) {
  10.     dep[u] = dep[p] + 1;
  11.     up[u][0] = p;
  12.  
  13.     // Tự tính tổ tiên ngay trong lúc DFS
  14.     for(int i=1; i<20; ++i)
  15.         up[u][i] = up[up[u][i-1]][i-1];
  16.  
  17.     for(int v : adj[u]) {
  18.         if(v != p) dfs(v, u);
  19.     }
  20. }
  21.  
  22. int lca(int u, int v) {
  23.     // Đảm bảo u luôn sâu hơn v để dễ xử lý
  24.     if(dep[u] < dep[v]) swap(u, v);
  25.  
  26.     // Bước 1: Kéo u lên cho bằng độ sâu v
  27.     // Duyệt từ bước nhảy to nhất về nhỏ nhất
  28.     for(int i=19; i>=0; --i) {
  29.         if(dep[u] - (1<<i) >= dep[v]) 
  30.             u = up[u][i];
  31.     }
  32.  
  33.     if(u == v) return u;
  34.  
  35.     // Bước 2: Kéo cả 2 lên cùng lúc
  36.     // Chỉ nhảy khi sếp KHÁC nhau (nghĩa là chưa chạm phần chung)
  37.     for(int i=19; i>=0; --i) {
  38.         if(up[u][i] != up[v][i]) {
  39.             u = up[u][i];
  40.             v = up[v][i];
  41.         }
  42.     }
  43.  
  44.     // Lúc này u và v đang ở ngay dưới LCA -> Trả về bố của u
  45.     return up[u][0];
  46. }
  47.  
  48. int main()
  49. {
  50.     cin.tie(0)->sync_with_stdio(0);
  51.     if(fopen("Company_Queries_II.inp","r"))
  52.     {
  53.         freopen("Company_Queries_II.inp","r",stdin);
  54.         freopen("Company_Queries_II.out","w",stdout);
  55.     }
  56.  
  57.     cin >> n >> q;
  58.     for(int i=2; i<=n; ++i) {
  59.         int boss; cin >> boss;
  60.         adj[boss].push_back(i);
  61.     }
  62.  
  63.     // Gốc là 1, cha của gốc coi như là 0
  64.     dfs(1, 0);
  65.  
  66.     while(q--) {
  67.         int a, b;
  68.         cin >> a >> b;
  69.         cout << lca(a, b) << '\n';
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 9220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zYAVrz
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!