樱花树节点删除问题 题解

问题分析

我们有一棵以 $0$ 为根的有根树，每个节点 $i$ 有樱花数 $c_i$ 和儿子数 $\text{son}(i)$。每个节点有载重限制：

$$\text{son}(i) + c_i \leq m$$

删除节点时，该节点的樱花和儿子会连接到其未被删除的祖先节点。要求最大化删除的节点数（根节点不能删除）。

关键观察

1. 问题转化

删除节点相当于将其子树"合并"到某个未被删除的祖先。这实际上是一个树形贪心问题。

2. 节点价值表示

对于每个节点 $i$，定义其"价值"为：

$$\text{val}[i] = \text{son}(i) + c_i$$

这表示该节点当前占用的"载重单位"。

算法思路

1. 自底向上贪心

从叶子节点开始向上处理，对于每个节点：

将其所有子节点按 $\text{val}$ 值从小到大排序

依次尝试合并子节点，如果合并后不超过载重限制 $m$，就删除该子节点

2. 核心贪心策略

sort(v[now].begin(), v[now].end(), [](const int a, const int b) {
    return val[a] < val[b];
});

for (auto x : v[now]) {
    if (val[now] + val[x] - 1 <= m) {
        val[now] += val[x] - 1;
        ++ans;
    }
}

为什么按 $\text{val}$ 从小到大排序？

优先合并"价值"小的子树，可以合并更多节点

这保证了局部最优，进而得到全局最优

3. 合并操作分析

当节点 $now$ 合并子节点 $x$ 时：

$\text{val}[now]_{\text{new}} = \text{val}[now]_{\text{old}} + \text{val}[x] - 1$

减 $1$ 是因为子节点 $x$ 被删除后，$now$ 减少了一个儿子计数

正确性证明

贪心选择性质

假设有子节点 $a$ 和 $b$，且 $\text{val}[a] \leq \text{val}[b]$。如果先合并 $b$ 能获得最优解，那么先合并 $a$ 至少能获得相同的解，因为：

合并 $a$ 后剩余的载重更多

有更多机会合并其他节点

最优子结构

每个子树的最优删除方案独立，父节点的决策基于子树的局部最优解。

复杂度分析

时间复杂度：$O(n \log n)

DFS遍历：$O(n)$

每个节点的子节点排序：$O(\text{deg} \log \text{deg})$，总复杂度 $O(n \log n)$

空间复杂度：$O(n)$

样例解析

输入：

n=10, m=4
樱花数: [0,2,2,2,4,1,0,4,1,1]
树结构: 略

处理过程：

1.计算每个节点的 $\text{val}[i] = \text{son}(i) + c_i$

2.从叶子节点开始向上贪心合并

3.最终删除4个节点

输出：4

关键技巧

1.价值定义：$\text{val}[i] = \text{son}(i) + c_i$ 准确反映节点占用

2.贪心排序：按价值升序处理保证最优性

3.合并公式：$\text{val}[now] += \text{val}[x] - 1$ 正确更新载重

总结

本题通过巧妙的贪心策略解决了树形结构上的节点删除问题：

1.自底向上处理：符合树形问题的典型解法

2.价值排序贪心：保证每次合并都是局部最优选择

3.载重动态更新：准确反映合并后的状态变化

算法在 $O(n \log n)$ 时间内解决问题，适用于 $n \leq 2 \times 10^6$ 的大规模数据。