您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

HDU 2196 Computer 題解：樹狀 DP 求每節點最遠距離（兩次 DFS 遞推法）

編輯：關於C語言

HDU 2196 Computer 題解：樹狀 DP 求每節點最遠距離（兩次 DFS 遞推法）

題目連結：HDU 2196

一、題意重述

初始有 1 台電腦（節點 1）
後續加入 N-1 台（N ≤ 10000），每台連接既有電腦 a，連線長度 L
形成一棵樹（無環連通圖）
求每台電腦到所有其他電腦的最大距離

二、核心思路：樹上最遠點 = 直徑端點之一

對於樹上任一節點，其最遠節點必定是樹直徑的兩個端點之一。但本題採用經典兩次 DFS 遞推（換根 DP）直接求出每節點答案：

第一次 DFS（自底向上）：計算每節點作為根時，子樹內的最長與次長下行路徑長度 dp[u][0]、dp[u][1]
第二次 DFS（自頂向下）：利用父節點資訊，計算經由父節點向上再向下其他分支的路徑，更新各節點最終答案

三、演算法詳解

1. 第一次 DFS：`dfs(u, parent)`

void dfs(int u, int parent) {
    for (int e = head[u]; e; e = edges[e].next) {
        int v = edges[e].to, w = edges[e].w;
        if (v == parent) continue;
        dfs(v, u);
        // 以 v 為子根的最長路徑 + 邊權
        int cand = dp[v][0] + w;
        if (cand >= dp[u][0]) {
            dp[u][1] = dp[u][0];   // 原最長降為次長
            dp[u][0] = cand;       // 更新最長
        } else if (cand > dp[u][1]) {
            dp[u][1] = cand;       // 更新次長
        }
    }
}

dp[u][0]：u 子樹內最長下行距離
dp[u][1]：u 子樹內次長下行距離（需與最長來自不同子分支）

2. 第二次 DFS：`solve(u, parent)`

void solve(int u, int parent) {
    for (int e = head[u]; e; e = edges[e].next) {
        int v = edges[e].to, w = edges[e].w;
        if (v == parent) continue;

        // 判斷 v 是否在 u 的「最長鏈」上
        if (dp[u][1] == -1 || dp[u][0] - w != dp[v][0]) {
            // v 不在最長鏈：u 的最長路徑可直接給 v 使用
            dp[v][0] = dp[u][0] + w;
            dp[v][1] = -1;
        } else {
            // v 在最長鏈上：v 不能用 u 的最長，改用次長
            if (dp[u][1] + w >= dp[v][0]) {
                dp[v][0] = dp[u][1] + w;
                dp[v][1] = -1;
            } else {
                dp[v][1] = dp[u][1] + w;  // 保留 v 原最長，更新次長
            }
        }
        solve(v, u);
    }
}

關鍵判斷：dp[u][0] - w == dp[v][0] 表示 v 正是貢獻 u 最長路徑的那個孩子
若 v 在最長鏈上，v 的新最長只能來自 u 的次長（或 v 自身子樹）
遞推過程中直接覆蓋 dp[v][0]，因父節點傳來的路徑必定優於或等於原值

四、完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
const int INF = 0x3f3f3f3f;

int dp[N][2], ans[N];
int head[N], tot;

struct Edge { int to, w, next; } e[N << 1];

inline void add_edge(int u, int v, int w) {
    e[++tot] = {v, w, head[u]};
    head[u] = tot;
}

void dfs(int u, int pre) {
    dp[u][0] = dp[u][1] = -1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (v == pre) continue;
        dfs(v, u);
        int cand = dp[v][0] + w;
        if (cand >= dp[u][0]) {
            dp[u][1] = dp[u][0];
            dp[u][0] = cand;
        } else if (cand > dp[u][1]) {
            dp[u][1] = cand;
        }
    }
    if (dp[u][0] == -1) dp[u][0] = 0;  // 葉子節點
}

void solve(int u, int pre) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (v == pre) continue;
        if (dp[u][1] == -1 || dp[u][0] - w != dp[v][0]) {
            dp[v][0] = dp[u][0] + w;
            dp[v][1] = -1;
        } else {
            if (dp[u][1] + w >= dp[v][0]) {
                dp[v][0] = dp[u][1] + w;
                dp[v][1] = -1;
            } else {
                dp[v][1] = dp[u][1] + w;
            }
        }
        solve(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        memset(head, 0, sizeof(head));
        memset(dp, 0, sizeof(dp));
        tot = 0;
        for (int i = 2; i <= n; i++) {
            int a, L;
            cin >> a >> L;
            add_edge(i, a, L);
            add_edge(a, i, L);
        }
        dfs(1, -1);
        solve(1, -1);
        for (int i = 1; i <= n; i++)
            cout << dp[i][0] << '\n';
    }
    return 0;
}