自动搬运

查看原文

来自洛谷，原作者为

	szhlg 2023.9.25-2024.1.03

搬运于2025-08-24 22:22:26，当前版本为作者最后更新于2020-06-15 16:41:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么是黄题啊zbl，看来我已经弱到连黄题都不会了。。

感觉是一道比较好的构造题。

我们先分析一下题意吧。有两个集合，一个存着你选过的点，另一个存着你选点过程中的两点间路径的最小值。让你最大化所有选的点权 + 最小值的乘积。

值得注意的是，选过的点不论你选多少次都算一次，不代表你不可以选多个点。

好了，看了这个题，我一点思路都没有，于是开始看subtask。

直接输出0就可以得到1分。这就是我比赛的分数。

首先看链的部分分。先说一个结论：一定选的是这个链的一段前缀和一段后缀。

我们从左到右编号，从1~5。

首先考虑路径最小值怎么算。那显然是1~4的长度和2~5的长度的最小值。

这个可以这样想：我可以按照1、5、1、4、1、5、2这样的顺序去选。这样就保证了最大化距离的最小值。

然后如果选的不是一段前缀和一段后缀，那显然不如选上。因为这样最小距离是不变的，而点权变大了。

好了，链的部分就这些。

如果是树的话，类比链的情况，可以把直径找出来。像这样的图：

找到直径之后，假设那个红色的是直径，我们可以类比链的方法，每次构造选点的顺序，都是考虑走到距离你想选的点最远的那个点，然后再选那个点，然后再跳回距离你选的点最远的点。

这样每个点对于路径最小值的贡献，就是离这个点最远的点与这个点的距离。所以我们可以按照原来的思路，把每个点和距离他距离最远的点之间的距离算出来排序，最终统计答案。

显然距离每个点最远的点是直径两个端点中的一个。

这样就可以直接统计答案了，具体看代码82~91行。

复杂度是O（n log n），瓶颈在于排序。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using std::max;
using std::min;
using std::sort;
const int maxn = 300005;
struct stu{
	int to,nxt,w;
}sexy[600005];
long long ans;
int n,hd[maxn],cnt,a[maxn];
void add(int x,int y,int z)
{
	sexy[++cnt].to = y;
	sexy[cnt].nxt = hd[x];
	hd[x] = cnt;
	sexy[cnt].w = z;
}
int dep1[maxn],dep2[maxn],rt1,rt2,dep[maxn];
void dfs1(int x,int fa){
	for(int i=hd[x];i;i=sexy[i].nxt){
		int v = sexy[i].to;
		if(v == fa) continue;
		dep[v] = dep[x] + sexy[i].w;
		dfs1(v,x);
	}
}
struct akk{
	int as,bs;
}chz[maxn];
bool xtt(akk a,akk b){
	return a.as > b.as;
}
void dfs2(int x,int fa){
	for(int i=hd[x];i;i=sexy[i].nxt){
		int v = sexy[i].to;
		if(v == fa) continue;
		dep1[v] = dep1[x] + sexy[i].w;
		dfs2(v,x);
	}
}
int zhijing; 
void dfs3(int x,int fa){
	for(int i=hd[x];i;i=sexy[i].nxt){
		int v = sexy[i].to;
		if(v == fa) continue;
		dep2[v] = dep2[x] + sexy[i].w;
		dfs3(v,x);
	}
}
long long sum1[maxn],sum2[maxn]; 
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	} 
	dfs1(1,0);
	int maxx = 0; 
	for(int i=1;i<=n;i++){
		if(maxx < dep[i]){
			maxx = dep[i];
			rt1 = i;
		}
	}
	dfs2(rt1,0);
	maxx = 0;
	for(int i=1;i<=n;i++){
		if(maxx < dep1[i]){
			maxx = dep1[i];
			rt2 = i;
		}
	}
	dfs3(rt2,0); 
	for(int i=1;i<=n;i++){
		chz[i].as = max(dep1[i],dep2[i]);
		chz[i].bs = a[i];
	}
	sort(chz + 1,chz + n + 1,xtt);
	maxx = 0;
	for(int i=1;i<=n;i++){
		maxx += chz[i].bs;
		ans = max(ans,maxx * chz[i].as);
	}
	printf("%lld\n",ans);
}