「CF1637F」Towers

发表于 2025-03-17 更新于 2026-03-05 分类于 Codeforces 本文字数： 431 阅读时长 ≈ 2 分钟

Description

给出一棵包含 $n$ 个点的树，编号 $1 \sim n$ 。第 $i$ 个点的高度为 $h_i$ 。

你可以在任意点放置任意数量的塔，对于每个塔，你可以选择放在哪个点，并且可以选择它的效率。设置一个效率为 $e$ 的塔需要花费 $e$ 金币，其中 $e > 0$ 。

如果存在一对分别位于 $u, v$ ( $u \neq v$ ) 的信号塔，它们的效率分别为 $e_u, e_v$ ，且满足 $\min(e_u, e_v) \geq h_x$ ，且点 $x$ 位于从 $u$ 到 $v$ 的路径上，则我们认为 $x$ 能够收到信号。

请你求出使得所有顶点都接收到信号，所需的最小金币数。

数据范围： $2 \leq n \leq 2 \times 10^5$ ， $1 \leq h_i \leq 10^9$ 。

时空限制： $2$ s / $256$ MiB。

Solution

注意到，叶子节点处是一定要建造塔的，否则该叶子一定无法被覆盖到。其次，非叶子节点处是不必建塔的（因为不如把非叶子节点的塔挪到叶子节点）。

考虑以 $h$ 值最大的节点作为根节点 $\mathrm{rt}$ ，则根节点必须要有两个不同的子树均包含 $\geq h_{\mathrm{rt}}$ 的塔，其他点 $u$ 则只需要保证子树内包含 $\geq h_u$ 的塔即可（因为 $u$ 的子树外一定有一个 $\geq \max h$ 的塔）。

从下往上贪心，每次贪心地考虑子树 $u$ 内已放置的塔的最大值 $\mathrm{mx}$ ，若 $\mathrm{mx} \geq h_u$ 就不用管，否则将 $\mathrm{mx}$ 替换为 $h_u$ 即可。特别地，根节点需要考虑子树内已放置的塔的最大值与次大值（需要来自两个不同的子树）。