HDU 2196 Computer - 樹形 DP 求每節點到最遠節點距離

題目大意

給定一棵 N (≤10000) 節點的樹，邊有權長。節點 1 為根。對每個節點 i，求其到樹中最遠節點的距離 S_i（即以 i 為根的樹的高度，邊權和）。

樹形 DP 兩遍掃描法

經典「樹上最遠點」問題：

1. 第一遍 DFS (自底向上)：計算 down[u] = u 子樹內到最遠葉子的距離。同時記錄每條邊對應的子樹貢獻 edgeContrib[u][v] = down[v] + w(u,v)。
2. 第二遍 DFS (自頂向下)：計算 up[u] = 通過父節點方向到最遠點的距離。對節點 u，其最遠距離 ans[u] = max(down[u], up[u])。
   遞推：up[v] = w(u,v) + max(up[u], max_{兄弟 x≠v} edgeContrib[u][x])。

代碼實現 (C++)

#include 
using namespace std;

const int MAXN = 10005;
struct Edge { int to, w; };
vector G[MAXN];
int N;
int down[MAXN], up[MAXN], ans[MAXN];
int best1[MAXN], best2[MAXN], bestChild[MAXN]; // 子樹最大/次大貢獻及對應孩子

void dfs1(int u, int fa) {
    down[u] = 0;
    for (auto &e : G[u]) {
        int v = e.to, w = e.w;
        if (v == fa) continue;
        dfs1(v, u);
        int val = down[v] + w;
        if (val > best1[u]) {
            best2[u] = best1[u];
            best1[u] = val;
            bestChild[u] = v;
        } else if (val > best2[u]) {
            best2[u] = val;
        }
    }
    down[u] = best1[u];
}

void dfs2(int u, int fa) {
    ans[u] = max(down[u], up[u]);
    for (auto &e : G[u]) {
        int v = e.to, w = e.w;
        if (v == fa) continue;
        // 通過父節點方向的最遠距離
        int use = (v == bestChild[u]) ? best2[u] : best1[u];
        up[v] = w + max(up[u], use);
        dfs2(v, u);
    }
}

int main() {
    while (cin >> N) {
        for (int i = 1; i <= N; ++i) {
            G[i].clear();
            down[i] = up[i] = ans[i] = 0;
            best1[i] = best2[i] = bestChild[i] = 0;
        }
        for (int i = 2; i <= N; ++i) {
            int p, w; cin >> p >> w;
            G[i].push_back({p, w});
            G[p].push_back({i, w});
        }
        dfs1(1, 0);
        up[1] = 0;
        dfs2(1, 0);
        for (int i = 1; i <= N; ++i) cout << ans[i] << '\n';
    }
    return 0;
}

關鍵點

• 記錄每個節點的「最大子樹貢獻」與「次大子樹貢獻」，第二遍 DFS 時 O(1) 獲取兄弟方向最大值，避免 O(度²) 循環。
• up[根] = 0，葉子節點 down=0，邏輯統一。
• 邊權可為任意非負整數，總和 ≤ 1e9，用 int 或 long long。

複雜度

• 時間：O(N) — 兩次 DFS，每條邊常數次處理。
• 空間：O(N)

總結

樹上每節點最遠距離是樹形 DP 經典模板題。「一遍向下算子樹最遠，一遍向上算父方向最遠，合併取最大」是核心套路。記錄最大/次大子樹貢獻是優化關鍵，將二遍 DFS 降為 O(N)。面試必會，可延伸至「樹的直徑」、「樹上最近公共祖先」、「重心分解」等進階專題。