HDU 4714 Tree2cycle 樹轉環最小代價 樹形DP/貪心

問題描述

給定一棵 n 個節點的樹，操作：斷開一條邊或連接一條邊，代價均為 1。求將樹轉化為簡單環（每個節點度數為 2，連通，n 條邊）的最小代價。

核心觀察

環要求每個節點度數恰好為 2。樹中度數 > 2 的節點必須斷開多餘邊；度數 < 2 的節點需要連接新邊。
每個度數為 d 的節點：
- 若 d > 2：需斷開 d - 2 條邊
- 若 d = 1：需連接 1 條邊（葉子）
- 若 d = 2：無需操作

DFS 計算答案

對於每個節點 u，統計其子樹中「需要向父節點連接邊」的數量 need。
葉子節點返回 1（需要連接父節點）。
內部節點收集子節點返回值，若 sum ≥ 2：
- 根節點：代價 += (sum - 2) × 2，返回 0
- 非根：代價 += (sum - 1) × 2，返回 0
否則返回 sum（向上傳遞需求）。

代碼實現

int dfs(int u) {
    vis[u] = 1;
    int sum = 0;
    for (int v : adj[u]) if (!vis[v])
        sum += dfs(v);
    
    if (sum >= 2) {
        if (u == 1) ans += (sum - 2) * 2;
        else ans += (sum - 1) * 2;
        return 0;
    }
    return sum; // 0 或 1
}

int main() {
    // 讀入樹，建圖
    ans = 0;
    dfs(1);
    printf("%d\n", ans);
}

原理說明

每個返回 1 的子樹代表一條「懸掛鏈」需要接入環中。節點處理多條懸掛鏈時，保留最多 2 條（根保留 2，非根保留 1），其餘必須斷開並重新連接，每多一條產生代價 2（一斷一連）。

複雜度

單次 DFS O(n)，遞歸深度可能達 n，需增大棧或用迭代實現。