HDU 2586：LCA轉RMQ模板題——樹上兩點距離查詢

題目簡述

給定一棵帶權樹（N≤40000），回答M個查詢：求任意兩節點間的最短距離。保證圖連通，無需處理不連通情況。

標準解法：LCA + RMQ (ST表)

步驟與HDU 2874類似，但無需並查集與虛擬節點：

1. 從任意節點（如1）為根DFS，記錄Euler序列E[]、深度L[]、首次出現H[]、根距離dis[]。
2. 構建ST表預處理RMQ，查詢區間最小深度對應的節點即為LCA。
3. 距離公式：dis[u] + dis[v] - 2*dis[lca(u,v)]。

代碼要點對比

• 數組大小：MAXN=40010，Euler序列長度2*N-1。
• DFS起點固定為1，vis[1]=true，深度從1開始。
• RMQ初始化長度為2*n-1。
• 多測試用例外層讀T，每輪清空圖與陣列。

精簡實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40010;
struct Edge { int to, w; };
vector<Edge> G[MAXN];
int dp[MAXN*2][20], L[MAXN*2], E[MAXN*2], H[MAXN], dis[MAXN];
bool vis[MAXN];
int n, m, k;

void dfs(int u, int dep) {
    vis[u] = true;
    E[++k] = u; L[k] = dep; H[u] = k;
    for (auto &e : G[u]) if (!vis[e.to]) {
        dis[e.to] = dis[u] + e.w;
        dfs(e.to, dep+1);
        E[++k] = u; L[k] = dep;
    }
}

void rmq_init(int len) {
    for (int i=1; i<=len; ++i) dp[i][0] = i;
    for (int j=1; (1<<j)<=len; ++j)
        for (int i=1; i+(1<<j)-1<=len; ++i)
            dp[i][j] = (L[dp[i][j-1]] < L[dp[i+(1<<(j-1))][j-1]]) ? dp[i][j-1] : dp[i+(1<<(j-1))][j-1];
}

int lca(int u, int v) {
    u = H[u]; v = H[v];
    if (u > v) swap(u, v);
    int k = 31 - __builtin_clz(v - u + 1);
    return (L[dp[u][k]] < L[dp[v-(1<<k)+1][k]]) ? E[dp[u][k]] : E[dp[v-(1<<k)+1][k]];
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i=1; i<=n; ++i) G[i].clear();
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        for (int i=1; i

總結
HDU 2586是LCA轉RMQ的標準模板題，掌握Euler序列+ST表的構建與查詢細節，可舉一反三解決樹上路徑查詢問題。