本文主要是介绍2020牛客暑期多校训练营（第九场）B Groundhog and Apple Tree —— 贪心，树形DP思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
现在有一棵树，你要从1开始跳一遍所有的点并且每条边只能走两次，再回到1，每条边都有一个边权，你走过这条边会先消耗wi点HP，每个点都有一个果子，吃掉这个果子会上升ai点HP，你在任何时候的HP不能小于0.并且你如果休息一秒钟会恢复1点HP。问你最少要休息多少时间才能走完这棵树。
题解：
赛场上还想着二分，二分个毛线。还有情况把自己绕晕了，我果然不适合做模拟题。
首先我们肯定是遍历这棵树，然后一个点有多个儿子，我们需要按最优的顺序去遍历这个儿子，那么每个儿子都有两个权值：
ned：遍历完这个儿子最少需要的初始体力
ad：遍历完这个儿子能够加上多少体力
然后这个需要排个序，排序方式是：
1.首先对于增加体力为正的情况，那么一定在前面，然后所有的正的按照ned从小到大排序。
2.对于增加体力为负的情况，我们就需要按照ned+ad从大到小排序
就像下面这张图：
绿色线以前都是ad是正的情况，绿色线以后都是ad为负的情况。我们已经知道了从前往后ad为正的时候，ned要从小到大，那么如果我们从后往前看，是不是就是ned+ad要从小到大。那么翻回来就是ned+ad要从大到小排序。
排序完后从前往后遍历一遍，最低点就是所需要的最小ned。因为我们这个是最优解了，所以不需要二分。
然后注意每个儿子的ned需要重新计算一遍：
v.ned=max(e[i].v,max(e[i].v-a[ne]+v.ned,2*s_w[ne]-s_ad[ne]+2*e[i].v));
e[i].v表示儿子子树的加血太多了，ned只需要这条边
e[i].v-a[ne]+v.ned表示是儿子的贡献是正的情况
2*s_w[ne]-s_ad[ne]+2*e[i].v表示儿子的贡献是负的情况
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
struct edge{int to,next;ll v;
}e[N*2];
int cnt,head[N];
void add(int x,int y,ll v){e[cnt].to=y;e[cnt].next=head[x];e[cnt].v=v;head[x]=cnt++;
}
struct node{ll ned,ad;bool operator< (const node& a)const {if(ad>=0){if(a.ad>=0)return ned<a.ned;return ad>a.ad;}if(a.ad>=0)return ad>a.ad;return ned+ad>a.ned+a.ad;}
};
ll a[N],s_w[N],s_ad[N];
node dfs(int x,int fa){vector<node>vec;s_ad[x]=a[x];for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa)continue;node v=dfs(ne,x);v.ned=max(e[i].v,max(e[i].v-a[ne]+v.ned,2*s_w[ne]-s_ad[ne]+2*e[i].v));v.ad=s_ad[ne]-2*s_w[ne]-2*e[i].v;s_w[x]+=s_w[ne]+e[i].v,s_ad[x]+=s_ad[ne];vec.push_back(v);}if(vec.size()){sort(vec.begin(),vec.end());ll ned=0,mi=0;for(node i:vec){ned-=i.ned;mi=min(mi,ned);ned+=i.ned+i.ad;}vec.clear();return {-mi,s_ad[x]-2*s_w[x]};}return {0,a[x]};
}
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);cnt=0;for(int i=1;i<=n;i++)s_w[i]=s_ad[i]=0,head[i]=-1;int x,y;ll v;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<n;i++)scanf("%d%d%lld",&x,&y,&v),add(x,y,v),add(y,x,v);printf("%lld\n",max(0ll,dfs(1,0).ned-a[1]));}return 0;
}这篇关于2020牛客暑期多校训练营（第九场）B Groundhog and Apple Tree —— 贪心，树形DP思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
