題意#
給你一棵有 \(n\) 個節點的樹，然後會有 \(q\) 筆詢問。每次詢問給定兩個節點 \(a\) 和 \(b\)，要求找出這兩個節點在樹上的最短距離。
思路#
這題其實就是在考我們怎麼快速在一棵樹上找距離。因為樹的特性是任兩點之間只有一條簡單路徑，所以不用動用到什麼 Dijkstra 或是 BFS 來慢慢找。
我們可以換個角度想，如果我們把整棵樹「拎起來」（選節點 1 當作根節點），每個點自然就會有各自的深度。要算 \(a\) 到了 \(b\) 的距離，其實就是看他們各自往上走，走到他們「最低的共同祖先（LCA）」要花幾步。
所以重點就變成怎麼找 LCA 了。我自己最習慣也是最推薦的寫法是「倍增法（Binary Lifting）」。
做法是建一個 par[i][j] 表格，記錄「節點 \(j\) 往上跳 \(2^i\) 步會到哪個點」。這樣我們在找 LCA 的時候，就能用類似二分搜的概念，從大步開始跳慢慢逼近答案，把時間複雜度壓下來。
算出 LCA 之後，距離公式就順理成章了：距離 = a 的深度 + b 的深度 - 2 * LCA 的深度
因為我們等於來回走了一趟 LCA，要把它的深度扣掉兩次。大概的邏輯就這樣。
程式碼#
#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<int> dep;
vector<vector<int>> par, v;
// 利用 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 和 b 調整到同樣的深度
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];
// 最後再往上踩一步，那就是 LCA 啦
return par[0][a];
}
signed main() { WA();
int n, q; cin >> n >> q;
int k = n-1;
v.resize(n+1);
while (k--) {
int a, b; cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
// par[i][j] 代表節點 j 往上跳 2^i 步會到達的節點
par.resize(20, vector<int>(n+1));
dep.resize(n+1);
// 從節點 1 開始 DFS，自己當自己的父親（根節點）
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;
// 代入剛才的距離公式：dep[a] + dep[b] - 2*dep[LCA]
cout << dep[a] + dep[b] - 2*dep[lca(a, b)] << '\n';
}
}
