題意#
有一間公司總共有 \(n\) 個員工。給你每個員工的直屬主管，接著會有 \(q\) 筆詢問，每次詢問給定這間公司的兩個員工，要你找出他們「層級最低的共同主管」是誰。
思路#
把公司層級畫出來，其實就是一棵樹，而這題要找的「共同主管」本質上完全就是樹上找「最低共同祖先（LCA）」的裸題。
既然是求 LCA，最暴力的方法當然是兩個人一步一步往上爬，看誰先碰到誰。但這在測資大的時候一定會 TLE。所以我們需要拿出找 LCA 的神器：「倍增法（Binary Lifting）」。
因為每次只跳一步太慢了，我們就準備一張小抄 par[i][j]，記錄每個員工往上跳 \(2^i\) 階的主管是誰。
這樣在查詢的時候，我們可以先讓比較底層的員工往上跳到跟另一個人同階級。接著兩個人再看著小抄，用二分搜的概念「一次跳一大步」，以最快速度逼近他們共同的主管。
這題的概念很單純，把樹建好、DFS 跑一次建立基本的深度表，然後用迴圈推敲出倍增表，最後處理查詢，就搞定了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
vector<vector<int>> v, par;
vector<int> dep;
// 跑一次 DFS 把每個人的深度跟直屬主管找出來（往上跳 2^0 步）
void dfs(int x, int u) {
par[0][x] = u;
for (auto &i : v[x]) {
if (i == u) continue; // 不要找回自己主管
dep[i] = dep[x]+1;
dfs(i, x);
}
}
// 找 a 和 b 的最低共同祖先 (LCA)
int lca(int a, int b) {
// 固定讓 a 都是比較深層（職位比較低）的那個員工
if (dep[a] < dep[b]) swap(a, b);
// 步驟 1：把 a 往上提拔，兩個人先平起平坐
for (int i = 19; i >= 0; i--) if (dep[par[i][a]] >= dep[b]) a = par[i][a];
if (a == b) return a; // 如果 a 居然直接變成了 b，那代表 b 原本就是上司
// 步驟 2：兩個人看著倍增表一起往上跳，直到抵達 LCA 的正下方
for (int i = 19; i >= 0; i--) if (par[i][a] != par[i][b]) a = par[i][a], b = par[i][b];
// 往上再推一階，就是真正的共同主管
return par[0][a];
}
signed main() { WA();
int n, q; cin >> n >> q;
v.resize(n+1);
// 題目說員工編號從 2 開始，第 i 個員工隸屬於主管 k
for (int i = 2; i <= n; i++) {
int k; cin >> k;
v[i].pb(k);
v[k].pb(i);
}
// par[i][j] 代表節點 j 往上跳 2^i 步的主管是誰
par.resize(20, vector<int>(n+1));
dep.resize(n+1);
// 從大老闆（節點 1）開始建樹，假設大老闆的主管是自己
dfs(1, 1);
// 建立倍增表：往上跳 2^i 步，等同於先跳 2^(i-1) 步，再往上跳 2^(i-1) 步
for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++) {
par[i][j] = par[i-1][par[i-1][j]];
}
while (q--) {
int a, b; cin >> a >> b;
cout << lca(a, b) << '\n';
}
}
