本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-29 22:05:29
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;
}
鲁ICP备2025150228号