2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp，贪心)

Groundhog and Apple Tree

题目描述

样例

input:
1
5
4 2 1 5 7
1 2 4
1 3 5
4 2 9
5 2 3
output:
23

题目大意

给定一棵树，每条边有权值，点上也有权值。现有一个初始$Hp=0$的人，如果经过边，那么$Hp$减去边权，如果经过点，那么会加上点权。为了保证任何时刻$Hp\ge 0$，他可以随时休息1分钟，然后增加1$Hp$。如果每个点的点权只能加一次，每条边只能经过两次，那么如果这个人从1号结点开始，遍历所有点回到1号结点所需要休息的最多时间是多少。

分析

我们考虑遍历整棵树意味着什么。
首先肯定是遍历根，然后挑一个子树遍历，最后回到根，然后再挑一个遍历。那么对于每个子树其实遍历的方式是一样的。所以，遍历整棵树可以分成若干棵子树的遍历。这就是树形$dp$了。
那么我们要定义状态：

• req[i] 表示$i$结点为根的子树的答案。
• data[i] 表示遍历$i$的子树后$Hp$的变化，可能为负。

那么根据这个，可以写出$data$的转移式子：
$data[x]=\sum(data[son]-2*e.v)+val[x]$
其中$e.v$为边权，$val[x]$为$x$的点权。
$2$倍的边权是因为要遍历后再会来，肯定是经过2次的。

那么接下来就是$req$的转移。
可以假设当前的所有的$data$已经求出并且子树中的$req$也求好了，那么作为当前的结点，我们只要考虑先走哪个结点就可以了。首先肯定是先走$data\ge0$的子儿子，这样会有更多的$Hp$去走其他的子树，依此我们可以把所有的子儿子分成两部分：

• $part1$ $data\ge0$ ，那么对于这种子儿子，显然，我们应该先走$req$较小的，这样可以得到更多的$Hp$减少休息。
• $part2$ $data<0$，对于这种儿子的遍历顺序就有点难想了。也许相应的你会觉得先走$req$较大的。但是显然，如果$data$不计的话，很容易找到一组数据可以把这个方法hack掉。因此对于这种，我们需要先走$req+data$较大的，这样可以保证休息得更少。这里可以自己推一下，易得嘛。

所以这样跑一遍树形dp就可以了。
然后有一点要注意：每个节点到子儿子的路径上的边权是要考虑的，所以不妨直接将他们存在$data,req$里面，具体的方法见代码。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
struct node{
	int to;ll v;
	node(){}
	node(int _to,ll _v){
		to=_to;v=_v;
	}
	bool friend operator<(node a,node b){
		return a.v<b.v;
	}
};
ll val[MAXN],req[MAXN],data[MAXN];
vector<node> vec[MAXN];
void dfs(int x,int fa)
{
	data[x]=val[x];req[x]=0;
	vector<pair<ll,node> > vp1,vp2;//vp1 part1,vp2 part2
	for(int i=0;i<vec[x].size();i++){
		node s=vec[x][i];
		if(s.to==fa) continue;
		dfs(s.to,x);
		data[s.to]-=s.v*2;
		//由于当前这条边要走两遍，所以可以直接压到子儿子里时要*2
		req[s.to]+=s.v;
		//这里由于只要考虑能不能走到子儿子就可以了，req是需要准备的Hp，所以不用*2
		data[x]+=data[s.to];
		if(data[s.to]>=0) vp1.push_back(make_pair(req[s.to],s));
		else vp2.push_back(make_pair(req[s.to]+data[s.to],s));
	}
	sort(vp1.begin(),vp1.end());
	sort(vp2.begin(),vp2.end());
	reverse(vp2.begin(),vp2.end());//倒序
	ll now=val[x];
	for(int i=0;i<vp1.size();i++){
		node son=vp1[i].second;
		if(now<req[son.to]) req[x]+=req[son.to]-now,now=req[son.to];
		now+=data[son.to];//减去需要的Hp，然后加上遍历后能得到的Hp
		if(now<0) req[x]+=-now,now=0;//如果走着走着变成负了，要调成正的
	}for(int i=0;i<vp2.size();i++){
		node son=vp2[i].second;
		if(now<req[son.to]) req[x]+=req[son.to]-now,now=req[son.to];
		now+=data[son.to];
		if(now<0) req[x]+=-now,now=0;//同上
	}
}
int main()
{
	int t,n,x,y;ll z;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0;i<=n;i++) vec[i].clear();//记得清零！！！
		for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
		for(int i=1;i<n;i++){
			scanf("%d%d%lld",&x,&y,&z);
			vec[x].push_back(node(y,z));
			vec[y].push_back(node(x,z));
		}
		dfs(1,-1);
		printf("%lld\n",req[1]);
	}
}

END

本文地址：https://blog.csdn.net/zhangchizc/article/details/107897532