BZOJ 2097 Exercise 奶牛健美操：二分答案 + 樹形 DP + 貪心刪邊

問題描述

給定一棵 N 節點樹，可刪除 k 條邊，將樹分裂成森林。求：森林中所有樹的直徑的最大值的最小可能值。

核心思路：二分答案 + 貪心檢查

「最大值最小」 → 二分答案。設二分的直徑上限為 limit。檢查：能否刪除 ≤ k 條邊，使每棵子樹直徑 ≤ limit？

檢查函數：樹形 DP 自底向上

對每個節點 u，收集所有子樹經過 u 向上延伸的最長鏈長度 dis[v] + 1（v 為子節點）。將這些長度排序。

貪心策略：從大到小刪除最長鏈，直到剩下的最長兩條鏈之和 ≤ limit，且單條最長鏈 ≤ limit。被刪除的鏈對應刪掉連接該子樹的邊，計數 ans++。最終向父節點返回剩餘的最長鏈長度（或 0）。

遞歸邏輯

void Tree_DP(int x, int limit) {
    int bottom = top;                 // 記錄棧底
    for (子節點 v) {
        if (v == fa[x]) continue;
        fa[v] = x;
        Tree_DP(v, limit);
        stack[++top] = dis[v] + 1;    // 收集子鏈長度
    }
    sort(stack+bottom+1, stack+top+1); // 升序

    // 從大到小刪除
    for (int i = top; i > bottom; i--) {
        if (stack[i] > limit || (i > bottom+1 && stack[i] + stack[i-1] > limit))
            ++ans;                    // 刪掉這條邊
        else break;                   // 剩餘合法
    }
    dis[x] = (i == bottom) ? 0 : stack[i]; // 向上返回最長合法鏈
    top = bottom;                     // 恢復棧
}

二分邊界與主程序

int Bisection() {
    int l = 1, r = n;                 // 直徑範圍 [1, n]
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        ans = 0; Tree_DP(1, mid);
        if (ans > m) l = mid;         // 刪邊太多，limit 太小
        else r = mid;
    }
    ans = 0; Tree_DP(1, l);
    if (ans <= m) return l;
    return r;
}

複雜度分析

• 每次 Tree_DP：O(N log N)（排序），實際可用計數排序/桶排序優化到 O(N)，但 N log N 通常足夠。
• 二分次數：O(log N)。
• 總：O(N log² N) 或 O(N log N)。

常見錯誤與調試

• 二分邊界條件寫錯：while (l+1 避免死循環，最後驗證 l 和 r。
• 排序方向：升序後從右向左遍歷（從大到小刪）。
• 返回值 dis[x]：若無合法子鏈則 0，否則為最大的合法子鏈長度。
• 全局變量 ans 每次 check 前歸零。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;

struct Edge { int to, next; } table[M<<1];
int head[M], tot;
int n, m, ans;
int fa[M], dis[M], stack[M], top;

void Add(int x, int y) { ... }

void Tree_DP(int x, int limit) { ... } // 如上

int Bisection() { ... } // 如上

int main() {
    int i, x, y;
    cin >> n >> m;
    for (i=1; i<n; i++) scanf("%d%d", &x, &y), Add(x,y), Add(y,x);
    printf("%d\n", Bisection());
    return 0;
}