HDU 2586 How far away？：離線 LCA (Tarjan 算法) 模板題

題目大意

樹上帶權邊，多次查詢兩節點間距離。n ≤ 40000, m ≤ 200, T ≤ 10。

Tarjan 離線 LCA 算法

1. DFS 遍歷樹，維護并查集合併已訪問子樹。
2. 訪問節點 u 時，標記 `vis[u]=true`，並查集 `fa[u]=u`。
3. 檢查所有以 u 為端點的查詢：若另一端點 v 已訪問 (`vis[v]`)，則 `LCA(u,v) = find(v)`。
4. 遞歸訪問子節點，回溯時 `fa[child] = u` 合併並查集。
5. 距離 = `dist[u] + dist[v] - 2*dist[lca]`。

代碼實現 (C++)

#include 
#include 
const int MAXN = 40005;

struct Edge { int to, w, next; } e[MAXN * 2];
int head[MAXN], ecnt;

int fa[MAXN], dist[MAXN], lca[MAXN];
bool vis[MAXN];
int q_u[MAXN], q_v[MAXN];

void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]}; head[u] = ecnt++;
    e[ecnt] = {u, w, head[v]}; head[v] = ecnt++;
}

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }

void tarjan(int u) {
    vis[u] = true; fa[u] = u;
    // 處理查詢
    for (int i = 1; i <= m; i++) { // 此處假設全局 m, q_u, q_v
        if (q_u[i] == u && vis[q_v[i]]) lca[i] = find(q_v[i]);
        if (q_v[i] == u && vis[q_u[i]]) lca[i] = find(q_u[i]);
    }
    // 遞歸子樹
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!vis[v]) {
            dist[v] = dist[u] + e[i].w;
            tarjan(v);
            fa[v] = u; // 合併
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        ecnt = 0; memset(head, -1, sizeof(head));
        for (int i = 1; i < n; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
        }
        for (int i = 1; i <= m; i++) scanf("%d%d", &q_u[i], &q_v[i]);
        memset(vis, 0, sizeof(vis));
        memset(dist, 0, sizeof(dist));
        tarjan(1); // 假設 1 為根
        for (int i = 1; i <= m; i++) {
            printf("%d\n", dist[q_u[i]] + dist[q_v[i]] - 2 * dist[lca[i]]);
        }
        if (T) printf("\n"); // 測試用例間空行
    }
    return 0;
}

關鍵點

• 離線算法：一次 DFS 解決所有查詢，O((n+m) α(n))。
• 並查集合併方向：子樹合併到父節點 (`fa[child]=u`)，保證 `find` 返回當前已訪問子樹的最高祖先 (即 LCA)。
• 查詢存儲：端點數組 `q_u`, `q_v`，DFS 時遍歷所有查詢檢查另一端是否已訪問。m≤200 遍歷查詢列表無壓力；大 m 時需用鏈表掛載查詢到節點。
• 多測試用例間需輸出空行。