BZOJ 4027 兔子與櫻花：樹形貪心刪除節點

題目大意

給定一棵有根樹，每個節點有若干櫻花。可刪除節點，刪除後該節點的櫻花及其子樹全部掛到其父節點。要求每個節點最終的「櫻花數 + 子節點數」不超過 m。求最多能刪除多少節點。

貪心策略與狀態定義

對每個節點 x，定義：

• f[x]：以 x 為根的子樹中，在不刪除 x 的前提下，最多能刪除的節點數。
• g[x]：在達到 f[x] 的情況下，x 節點的最小「負重」（即櫻花數 + 子節點數）。

遞歸計算

1. 初始 f[x] = 0，g[x] = a[x] + 1（自身櫻花 + 自身作為子節點計 1）。
2. 對每個子節點 y 遞歸計算 f[y], g[y]。
3. 先累加所有子樹的最大刪除數：f[x] += f[y]；並累加子節點貢獻：g[x] += g[y]？

實際貪心選擇：對於子節點 y，若刪除 y，則 y 的負重 g[y] 會加到 x 上，但 y 本身被刪除（計入 f[x]）。為了讓 x 的負重盡可能小以便後續能刪除更多祖先節點，應優先刪除 g[y] - 1 較小的子節點。（-1 是因為 y 本身不再作為子節點計入 x 的子節點數）

算法流程

1. DFS 後序遍歷。
2. 對節點 x，收集所有子節點 y 的 cost = g[y] - 1。
3. 將 cost 從小到大排序。
4. 依次嘗試刪除：若 g[x] + cost ≤ m，則 f[x]++，g[x] += cost；否則停止。

正確性證明概要

子樹對父節點的影響僅在於「若刪除子樹根，其負重會加到父節點」。若某子樹不刪除最多節點，只能減少加到父節點的負重，但犧牲了子樹內部的刪除數。這種捨近求遠永遠不如直接不刪除該子樹根、而在子樹內部多刪除幾個節點來得划算。因此貪心策略最優。

代碼實現

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 2002002;

struct Edge { int to, next; } e[M];
int head[M], tot;
int n, m;
int a[M], f[M], g[M];
bool notRoot[M];

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

void dfs(int u) {
    int top = 0;
    static int stk[M];
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        dfs(v);
        f[u] += f[v];
        g[u]++; // 子節點數 +1
    }
    g[u] += a[u]; // 加上自身櫻花
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        stk[++top] = g[v] - 1; // 刪除 v 的代價
    }
    sort(stk + 1, stk + top + 1);
    for (int i = 1; i <= top; i++) {
        if (g[u] + stk[i] <= m) {
            f[u]++;
            g[u] += stk[i];
        } else break;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        int k; scanf("%d", &k);
        for (int j = 1; j <= k; j++) {
            int x; scanf("%d", &x);
            addEdge(i, x+1); // 題目節點從 0 開始
            notRoot[x+1] = true;
        }
    }
    for (int i = 1; i <= n; i++)
        if (!notRoot[i]) {
            dfs(i);
            cout << f[i] << '\n';
        }
    return 0;
}

複雜度分析

• 時間：O(n log n)（排序主導），n ≤ 2000000？實際數據範圍需確認，但排序每個節點的子節點，總複雜度 O(n log n)。
• 空間：O(n)。

總結

本題是典型的樹形貪心：通過定義「最大刪除數」和「最小負重」兩個狀態，將局部最優選擇（刪除代價最小的子節點）推廣到全局最優。關鍵在於證明「不刪除最多節點的子樹永遠不劣於犧牲子樹刪除數以減輕父節點負重」。