CF1637F Towers 做题记录

给定一棵 $n$ 个点的树，每个点有一个权值 $a_i$。

一个长度为 $n$ 的序列 $b$ 合法当且仅当 $\forall 1\le u\le n$，都存在两个整数 $x,y$ 满足：

• $1\le x,y\le n$；
• $x\not=y$；
• $u$ 在 $x$ 到 $y$ 的简单路径上；
• $\min(b_x,b_y)\ge a_u$；

输出所有合法的 $b$ 中最小的 $\sum b_i$。

$2\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。

首先不难发现只有叶子（一度点）的 $b_i\not=0$。

令 $a_i$ 最大的点 $rt$ 做根，那么其余的点 $u$ 只要满足在它子树内存在 $b_v\ge a_u$ 的 $v$ 即可。

那么按照深度从深往浅贪心，贪到 $u$ 时选 $u$ 子树内 $b_v$ 最大的 $v$ 让 $b_v\to \max(b_v,a_u)$ 即可。

最后选树中最大和次大的 $b_i$ 令它们为 $a_{rt}$ 即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=200005;

int n,a[S];
vector<int> g[S];
int val[S];
int mx[S],mx2[S];

void dfs(int u,int fa)
{
	bool f=false;
	for(int v:g[u])
	{
		if(v==fa) continue;
		f=true;
		dfs(v,u);
		if(val[mx[v]]>val[mx[u]]) mx2[u]=mx[u],mx[u]=mx[v];
		else if(val[mx[v]]>val[mx2[u]]) mx2[u]=mx[v];
	}
	if(!f) mx[u]=u;
	val[mx[u]]=max(val[mx[u]],a[u]);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y),g[y].push_back(x);
	}
	int rt=1;
	for(int i=1;i<=n;i++) if(a[i]>a[rt]) rt=i;
	dfs(rt,0);
	if(mx2[rt]==0) mx2[rt]=rt;
	val[mx[rt]]=val[mx2[rt]]=a[rt];
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=val[i];
	printf("%lld\n",ans);
	return 0;
}