CF1637F 题解

· · 题解

题目大意

有一颗 n 个点的树，每个点都有一个高度 h_i 。你可以建任意多个塔，每个塔有一个信号强度 e_i。你需要求当所有点都有一对 (u, v) 使得这个点在 (u, v) 的路径上且 \min(e_u,e_v)\geqslant h_x 时所有塔的信号强度和的最小值。

思路

显然，根结点能满足条件只需它的子树中信号强度最大的两个塔（不在同一子结点的子树中，只有一个子结点时建在根节点上）的信号强度都大于或等于根节点的高度即可。运用贪心的思想，根结点最高时这个式子取等于号。所以我们把最高的点设为根结点，向下递归。

如果这个点是根结点，那么取出信号强度最大的两个塔（不在同一子结点的子树中），将这两个塔的信号强度增加到这个点的高度（当根结点只有一个子结点时，认为信号强度第二大的塔的信号强度为 0，即建在根节点上）

如果这个点不是根结点，显然在根节点的另一个子结点的子树或根节点上的塔的信号强度 > 根结点的高度 > 这个点的高度，所以只需要将子树中最大信号强度的塔的信号强度提升到这结点的高度即可。

具体实现

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
long long n, u, v, root = 1;
vector<long long> G[200010]; // 存储树
long long h[200010]; // 高度
long long ans = 0; // 结果
int dfs(int u, int fa = -1) {
    int max1 = 0, max2 = 0; // 最大值和次大值
    for (int i = 0; i < G[u].size(); i++) if (G[u][i] != fa) {
        int maxh = dfs(G[u][i], u); // 递归
        if (maxh > max1) max2 = max1, max1 = maxh; // 判断最大值
        else if (maxh > max2) max2 = maxh; // 判断次大值
    }
    if (fa != -1) ans += max(0ll, h[u] - max1), max1 += max(0ll, h[u] - max1); // 是子结点
    else ans += max(0ll, h[u] - max1) + max(0ll, h[u] - max2); // 是根结点
    return max1;
};
int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); // 输入高度
    for (int i = 1; i <= n; i++) if (h[i] > h[root]) root = i; // 找最高点
    for (int i = 1; i  < n; i++) {
        scanf("%lld%lld", &u, &v); // 输入边
        // 存图
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(root);
    printf("%lld\n", ans);
    return 0;
}