题解：POI 2011 Dynamite

问题本质

一棵 n 个节点的树

有些节点有炸药 (dᵢ = 1)

可以点燃 m 个节点（火从该节点开始同时向四周燃烧）

燃烧沿边传播，每条边需要 1 单位时间

火到达有炸药的节点时，炸药立即爆炸

求：所有炸药都被引爆的最短时间

核心思路：二分答案 + 贪心验证

1. 二分答案 二分最短时间 T，检查能否在 T 时间内用 ≤m 个点火点引爆所有炸药。

2. 如何验证(check)给定时间 T 用树形DP贪心判断：

定义状态：

down[u]: 从 u 的子树中最远的未覆盖炸药到 u 的距离（若子树内所有炸药都被覆盖则为 -∞）

up[u]: 从 u 到其子树中最近的点火点的距离（若子树无点火点则为 ∞）

还需要记录当前用了几个点火点 cnt

贪心规则：

对于节点 u，如果 down[u] = T（即最远的未覆盖炸药距离刚好为 T），那么必须在 u 点点火

因为如果再往上，这个炸药就来不及在 T 时间内被引爆

如果 u 有点火药且 up[u] > T 且 down[u] == -1（即自己未覆盖且上方点火点够不到），那么将 down[u] 设为 0（表示自己是未覆盖的炸药）

向上传递时：

up[fa] = min(up[所有子节点]) + 1

down[fa] = max(down[所有子节点]) + 1（只考虑未覆盖的）

最后检查根节点的未覆盖炸药距离：

如果根节点还有未覆盖的炸药(down[root] >= 0)，就需要在根点点火

3. 算法流程 text bool check(T): cnt = 0 树形DP: 叶子节点： 若有炸药: down = 0, up = ∞ 否则: down = -∞, up = ∞ 非叶子节点： 收集所有子节点信息 if down_child_max == T: // 必须点火 cnt++, up = 0, down = -∞ else: up = min(up_child) + 1 down = down_child_max + 1 if 节点有炸药 and up > T: down = max(down, 0) if down >= 0 and up <= down: // 被上方点火点覆盖 down = -∞ if down_root >= 0: cnt++ // 根节点需要点火 return cnt ≤ m
4. 时间复杂度 每次 check: O(n)

二分范围: 0 到 n

总复杂度: O(n log n)