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

题目大意

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

分析

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

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

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

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

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

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