自动搬运

查看原文

来自洛谷，原作者为

	nofind 苟到省选退役的蒟蒻

搬运于2025-08-24 21:50:19，当前版本为作者最后更新于2019-09-27 19:14:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意:https://www.luogu.org/problem/P3574

$f[x]$表示$x$子树内的最大值,$size[x]$表示走完$x$的子树后回到$x$的总时间

$f[x]=max(f[x],f[y]+size[x]+1)$($size[x]$存的是走完y之前的子树后回到$x$的时间)($+1$是从$x$到$y$的花费)

但是这样f的取值和遍历子树的顺序有关,于是考虑贪心

对于两个相邻(遍历时)的子树$y$和$z$,$y$前,$z$后

不交换:

$f[x]=max(f[x],size[x]+max(f[y],f[z]+size[y]+2)+1)$

交换:

$f[x]=max(f[x],size[x]+max(f[z],f[y]+size[z]+2)+1)$

如果交换比不交换优:

$max(f[z],f[y]+size[z]+2)<max(f[y],f[z]+size[y]+2)$

由于$f[z]<f[z]+size[y]+2,f[y]<f[y]+size[z]+2$

所以上式即为:

$f[y]+size[z]\not{+\not2}<f[z]+size[y]\not{+\not2}$

转化一下即为:$size[z]-f[z]<size[y]-f[y]$

排序即可

注意最后和size[1]+val[1]取max

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000010;
int n,cnt;
int val[maxn],head[maxn],f[maxn],size[maxn],tmp[maxn];
struct edge
{
	int to,nxt;
}e[maxn<<1];
inline bool cmp(int x,int y){return size[x]-f[x]<size[y]-f[y];}
inline void add(int u,int v)
{
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
void dfs(int x,int fa)
{
	if(x!=1)f[x]=val[x];
	for(int i=head[x];i;i=e[i].nxt)if(e[i].to!=fa)dfs(e[i].to,x); 
	int tot=0;
	for(int i=head[x];i;i=e[i].nxt)if(e[i].to!=fa)tmp[++tot]=e[i].to;
	sort(tmp+1,tmp+tot+1,cmp);
	for(int i=1;i<=tot;i++)f[x]=max(f[x],f[tmp[i]]+size[x]+1),size[x]+=size[tmp[i]]+2;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&val[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1,0);
	printf("%d",max(f[1],size[1]+val[1]));
	return 0;
}