CF1637F Towers 题解

· · 题解

CF1637F Towers 题解

题意

给你一棵树，树上的每一个节点都有一个高度，编号为 i 的点的高度为 h_i。你可以在这些点中选任意多的点建信号塔，建一座权值为 e 的塔花费为 e。

我们称一个点收到了信号，当且仅当存在一条路径，使得路径上的两个端点的权值都大于等于这个点的高度，问你令每个点都收到信号的最小花费。

思路

（温馨提示：下文中的高度并不是节点深度）

首先不难想到，每一座塔一定建在树的叶子上，因为任何非叶节点都能被叶节点替代。如果我在某个非叶节点上建了塔，为了满足要求，一定有另一个节点的权值大于等于这个节点的高度，那么我完全可以找到子树内的另一个叶节点，让它的权值大于等于当前节点的高度，这样的花费一定是更小的；另一方面，为了满足每个点都被覆盖的要求，每个叶节点一定有塔。所以，叶结点上一定有塔，而且只有叶结点上有塔。

上面的论述启发我们想到贪心的思路。首先，对于最大值，一定有两个叶节点上的塔的权值是最大值；对于其他的节点，我们令路径的一个端点是其中的一个最大值，另一个端点是当前节点子树内的某一个叶子，这样即可满足要求。

那么我们可以这么做：以一个高度最大的点为根，对于非根节点，如果当前节点的高度大于子树内的权值最大的塔的权值，那么就让这个权值变成当前节点的高度，否则不变；对于根节点，我们令整棵树权值最大的两个叶子的权值都变成最大的高度。不难证明，这样一定是最优的。

不理解可结合代码食用。

时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int h[N];
int ans;
vector<int> G[N];
int dfs(int u,int fa)
{
    int maxn1=0,maxn2=0;
    for(auto v:G[u])
    {
        if(v==fa) continue;
        int p=dfs(v,u);
        if(p>maxn1) maxn2=maxn1,maxn1=p;
        else if(p>maxn2) maxn2=p;
    }
    if(fa!=0) ans+=max(0ll,h[u]-maxn1);
    else ans+=max(0ll,h[u]-maxn1)+max(0ll,h[u]-maxn2);
    maxn1=max(maxn1,h[u]);
    return maxn1;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u); 
    }
    int s=1;
    for(int i=1;i<=n;i++)
    {
        if(h[i]>h[s]) s=i;
    }
    dfs(s,0);
    cout<<ans;
    return 0;
}