欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-01 10:31:42
Groundhog and Apple Tree题目描述样例input:154 2 1 5 71 2 41 3 54 2 95 2 3output:23题目大意给定一棵树,每条边有权值,点上也有权值。现有一个初始Hp=0Hp=0Hp=0的人,如果经过边,那么HpHpHp减去边权,如果经过点,那么会加上点权。为了保证任何时刻Hp≥0Hp\ge 0Hp≥0,他可以随时休息1分钟,然后增加1HpHpHp。如果每个点的点权只能加一次,每条边只能经过两次,那么如果这个人从1号结点开始,遍...

Groundhog and Apple Tree

题目描述

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

样例

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

题目大意

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

分析

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

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

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

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

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

所以这样跑一遍树形dp就可以了。
然后有一点要注意:每个节点到子儿子的路径上的边权是要考虑的,所以不妨直接将他们存在data,reqdata,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