HDU 4118：樹形 DP 最大化旅行距離和

題目大意

N 個城市由 N-1 條高速公路連成樹。每個城市有一人，需重新分配目的地（每城市恰好一人），使所有人旅行距離總和最大。輸出最大總距離。

解題思路

核心洞察：每條邊 (u,v) 將樹分為兩部分，設子樹大小為 sz，另一部分為 N-sz。該邊最多被遍歷 2 × min(sz, N-sz) 次（較小部分所有人必須跨邊，較大部分有人留下）。

對每條邊累加 weight × 2 × min(sz, N-sz) 即為答案。這等價於找樹的重心並交換兩側節點，奇數節點時重心與任一節點交換不影響總和。

算法實現

• DFS 計算子樹大小 num[u]。
• 遍歷每條邊累加貢獻。
• 注意：遞歸 DFS 可能棧溢出，需改用非遞歸（棧模擬）或增大棧。

參考代碼 (C++，非遞歸 DFS)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MAXN = 100005;

struct Edge { int v, w, next; } e[MAXN*2];
int head[MAXN], ecnt, n;
int num[MAXN], vis[MAXN], stk[MAXN];
LL ans;

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

void init() {
    fill(head, head+n+1, -1);
    ecnt = 0;
    ans = 0;
}

void dfsIterative(int root) {
    fill(vis, vis+n+1, 0);
    fill(num, num+n+1, 0);
    int top = 0;
    stk[top++] = root;
    vis[root] = 1;
    while (top > 0) {
        int u = stk[top-1];
        bool pushed = false;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (vis[v]) continue;
            stk[top++] = v;
            vis[v] = 1;
            pushed = true;
            break;
        }
        if (pushed) continue;
        // 後序處理
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (num[v]) {
                num[u] += num[v];
                ans += (LL)e[i].w * 2 * min(num[v], n - num[v]);
            }
        }
        num[u]++;
        top--;
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        scanf("%d", &n);
        init();
        for (int i = 1; i < n; ++i) {
            int x, y, z; scanf("%d%d%d", &x, &y, &z);
            addEdge(x, y, z);
            addEdge(y, x, z);
        }
        dfsIterative(1);
        printf("Case #%d: %lld\n", tc, ans);
    }
    return 0;
}