题解 [POI2014]FAR-FarmCraft

一发巧妙的贪心

在luogu网校学完这题，就来水题解。

容易看出，原图是一棵树。

所以我们考虑树形DP。

暴力DP肯定TLE，我们考虑用贪心优化。

我们记$g(i)$为遍历i的子树的最短时间。

$f(i)$为遍历i的子树，且每人装好电脑的最短时间。

显然有，$f(i)>g(i)$。

我们发现$f(i)-g(i)$这段时间是用来等待的。

如果你做过排队接水这道题，那么你不难想到要从大到小排序。

这样我们每次转移时可以先将儿子排序，然后直接转移。

但请注意细节，转移时：

for(int i=1;i<=cnt;i++) f[u]=max(f[u],f[son[i]]+g[u]+1);

而不是

for(int i=1;i<=cnt;i++) f[u]=max(f[u],f[son[i]]+g[u]+2)

为什么呢？

网校没讲，我想了好久QAQ。

其实很简单。

我们知道每个点的等待值肯定大于等于1（无特殊情况）。

所以$f[i]-g[i]>=1$。

我们只需考虑进入i时的一条道路。

而走出i时的时间已经被覆盖在等待时间里啦！

所以我们就可以轻松写出代码了qwq。

(至于具体的DP过程，可以写写这道题)。

#include <bits/stdc++.h>
using namespace std;
const int N=500009;
int f[N],g[N],son[N];
int n,cnt,tot;
int ver[N],nxt[N],h[N],a[N];
inline void add(int x,int y)
{
	ver[++tot]=y,nxt[tot]=h[x],h[x]=tot;
}
bool cmp(int x,int y)
{
	return f[x]-g[x]>f[y]-g[y];
}
inline void dfs(int u,int fa)
{
	if(u!=1) f[u]=a[u];
	for(int i=h[u];i;i=nxt[i]) if(ver[i]!=fa) dfs(ver[i],u);
	cnt=0;
	for(int i=h[u];i;i=nxt[i]) if(ver[i]!=fa) son[++cnt]=ver[i];
	sort(son+1,son+1+cnt,cmp);//贪心的想，f[i]-g[i]是需要等待的时间，根据排队接水，需要往前放。
	for(int i=1;i<=cnt;i++) f[u]=max(f[u],f[son[i]]+g[u]+1),g[u]+=g[son[i]]+2;
	//这个地方为什么f[son[i]]+g[u]要加1而不是2呢，我想了好久，详情请见我上面解析
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	printf("%d",max(f[1],g[1]+a[1]));
	return 0;
}