CF 1637F Towers

题目描述

https://codeforces.com/problemset/problem/1637/F

简要题意：给定一棵 $n$ 个节点的树，每个点有一个权值 $h$，现在要选择若干个点将其染色并赋一个值 $w$，要求染色之后，对于每个点 $x$，都存在两个染过色的点 $u$ 和 $v$，满足 $min\lbrace w_u,w_v\rbrace\ge h_x$ 且 $x$ 位于 $u$ 和 $v$ 的最短路径上，注意 $u$ 不能等于 $v$，如果给一个染色点赋值为 $x$，那么将产生 $x$ 花费，求最小花费

$n\le 2\times 10^5$

Solution

我们考虑树形 $DP$，但注意到一个点可能被与他没有祖先或儿子关系的点影响，我们首先尝试消除这一点

我们令权值最大的点为根，那么为了覆盖这个根，我们至少要选择它的两个儿子的子树内的点，我们首先默认这点存在

接下来我们开始从下往上做 $dp$，首先我们容易发现，我们只需要给叶子节点染色就行了，那么如果我们要覆盖 $u$，如果子树内目前的值不够，我们只需要选一个最大值提升到 $h_u$ 即可，因为外面还有另一个点，即用来覆盖根的那个点，而对于根，我们直接将最大和次大提升即可

#include <iostream>
#include <algorithm>
#define maxn 200010
#define ll long long
using namespace std;

int n, m, h[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

ll ans;
int dfs(int u, int fa) {
    int mx = 0, sm = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, t; if (v == fa) continue;
        t = dfs(v, u); 
        if (t > mx) sm = mx, mx = t; 
        else if (t > sm) sm = t; 
    }
    if (fa) ans += max(0, h[u] - mx);
    else ans += h[u] - mx + h[u] - sm;
    return max(mx, h[u]); 
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } int rt = max_element(h + 1, h + n + 1) - h; dfs(rt, 0);
    cout << ans << "\n";
    return 0;
}