题意
给一棵树，初始 (hp=0) 经过一条边会掉血 (w_i)，第一次到达一个点可以回血 (a_i) 在一个点休息 (1 s)可以回复 (1 hp) ，除此之外其他操作不消耗时间，血不能小于 (0)。每条边最多经过两次，求从起点经过所有点再回到起点到最小时间。
题目链接：https://ac.nowcoder.com/acm/contest/5674/B
分析
关键在于如何规划子树的访问顺序来优化问题的解。
在根节点恢复够了 (HP) 一定更优，
代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e5+5;
int a[N];
struct node
{
int id;
ll cost,gain;
bool operator < (const node b)const
{
if(gain>cost)
{
if(b.gain>b.cost) return cost<b.cost;
else return true;
}
else
{
if(b.gain>b.cost) return false;
else return gain>b.gain;
}
}
}dp[N];
vector<pii> pic[N];
void dfs(int u,int p)
{
vector<node>point;
for(int i=0;i<pic[u].size();i++)
{
pii tmp=pic[u][i];
if(tmp.second==p) continue;
dfs(tmp.second,u);
dp[tmp.second].id=tmp.second;
dp[tmp.second].cost+=tmp.first;
dp[tmp.second].gain-=tmp.first;
if(dp[tmp.second].gain<0)
{
dp[tmp.second].cost+=(-dp[tmp.second].gain);
dp[tmp.second].gain=0;
}
point.pb(dp[tmp.second]);
}
sort(point.begin(),point.end());//排序确定子树的访问顺序
ll now=a[u];
dp[u].cost=0;
for(int i=0;i<point.size();i++)
{
node tmp=point[i];
now-=tmp.cost;
if(now<0)
{
dp[u].cost+=(-now);
now=0;
}
now+=tmp.gain;
}
dp[u].gain=now;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
int u,v,w;
scanf("%d",&n);
for(int i=1;i<=n;i++)
pic[i].clear();
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
pic[u].pb(make_pair(w,v));
pic[v].pb(make_pair(w,u));
}
dfs(1,0);
printf("%lld
",dp[1].cost);
}
return 0;
}