「CF1637F」Towers
给出一棵包含 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。
时空限制:2s / 256MiB。
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 即可。特别地,根节点需要考虑子树内已放置的塔的最大值与次大值(需要来自两个不同的子树)。