本文章由 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;
}