2020牛客多校第九场

B.Groundhog and Apple Tree

显然，在中途恢复体力等价于在根节点将所有需要的体力恢复完再走。那么我们考虑树DP。(dp[u])表示遍历完(u)所在子树最少需要在(u)恢复的HP。(res[u])表示遍历(u)这个子树的收益（正就是获得HP，负就是需要HP）。我们需要确定的是一种访问子树的顺序。我们假设确定了一种访问顺序，考虑计算在此种情况下需要的恢复时间(need)。我们转移(dp[u])时，记录一个(sum[v]=res[v] - 2*w_{u,v})，表示从(u)点去访问子树(v)的收益。对于第(i)个访问的子树，我们需要起初至少有(H[i])点HP
那么(H[i]=cost[i]-sum_{j=1}^{i-1} sum[j])。其中(cost[i])表示从(u)遍历(i)子树需要的代价。
对于(cost[i])的计算，有(cost[i]=dp[i]+w_{u,i}+delta)，访问子树(i)的时候，可能从(i)回到(u)HP不够，需要一个(delta)的HP。我们如果在(u)恢复了(dp[i]+w_{u,i})的体力后访问子树，到(i)准备返回(u)的时候剩余(HP=dp[i]+w_{u,i}-w_{u,i}+res[i]=dp[i]+res[i])，如果(dp[i]+res[i]geq w_{u,i})，(delta=0)，否则(delta=w_{u,i}-dp[i]-res[i])。
此时求出每个(cost[i])和(H[i])。那么可以得到(need=max_{i=1}^{son[u]} H[i])。对于所有的排列方式，我们有(dp[u]=min(need))。
如果某个访问顺序是最优的，那么交换任意(i)和(i+1)都会不优。考虑交换(i)和(i+1)，改变的只有(H[i],H[i+1])，所以要有(max(cost[i]-sum_{j=1}^{i-1}sum[j],cost[i+1]-sum_{j=1}^{i} sum[j])leq max(cost[i+1]-sum_{j=1}^{i-1} sum[j] , cost[i]-sum_{j=1}^{i-1}sum[j]-sum[i+1])).方便观察，我们全部消去一个(A=sum_{j=1}^{i-1}sum[j]).原式化简为(max(cost[i],cost[i+1]-sum[i])leq max(cost[i+1],cost[i]-sum[i+1])).我们进行分类讨论。

(1.sum[i]<0,sum[i+1]<0),那么会有(cost[i+1]-sum[i]leq cost[i]-sum[i+1])即(cost[i]+sum[i]geq cost[i+1]+sum[i+1]).

(2.sum[i]geq 0,sum[i+1]geq 0),那么会有(cost[i]leq cost[i+1])

(3.sum[i]<0,sum[i+1]geq 0),恒不成立

(4.sum[i]geq 0,sum[i+1]<0),恒成立

综上，我们先讲所有子节点分成两类分别排序就可以确定访问顺序了。

#include <bits/stdc++.h>
#define pb emplace_back
#define ll long long
#define lson rt << 1
#define rson rt << 1 | 1
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

const int maxn = 2e5;
ll sum[maxn + 11],dp[maxn + 11],res[maxn + 11];
int to[maxn + 11],w[maxn + 11],front[maxn + 11],nxt[maxn + 11],a[maxn + 11];
int cnt = 0;

void add(int u,int v,int _) { to[++cnt] = v; w[cnt] = _; nxt[cnt] = front[u]; front[u] = cnt; }

void dfs(int x,int fa) {
	sum[x] = a[x]; res[x] = a[x];
	for (int i = front[x]; i ; i = nxt[i]) {
		int v = to[i] , _ = w[i];
		if (v == fa) continue;
		dfs(v , x);
		sum[v] -= 2 * _; sum[x] += sum[v];
		res[x] -= 2 * _; res[x] += res[v];
	}
}

void solve(int x,int fa) {
	dp[x] = 0;
	vector <pll> A,B; ll cost = 0 , sal = 0;
	for (int i = front[x]; i ; i = nxt[i]) {
		int v = to[i] , _ = w[i];
		if (v == fa) continue;
		solve(v , x);
		cost = dp[v] + _; if (res[v] + dp[v] - _ < 0) cost -= res[v] + dp[v] - _;
		sal = sum[v];
		if (sal >= 0) A.pb(make_pair(cost , sal)); else B.pb(make_pair(cost , sal));
	}
	sort(all(A) , [&](pll x,pll y) { return x.first < y.first; } );
	sort(all(B) , [&](pll x,pll y) { return x.first + x.second > y.first + y.second; } );
	ll s = 0;
	for (auto pi : A) dp[x] = max(dp[x] , pi.first - s) , s += pi.second;
	for (auto pi : B) dp[x] = max(dp[x] , pi.first - s) , s += pi.second;
	dp[x] -= a[x]; dp[x] = max(dp[x] , 0ll);
} 

int main(){ 
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i] , front[i] = 0;
		cnt = 0;
		for (int i = 1; i < n; i++) {
			int u , v , w; cin >> u >> v >> w;
			add(u , v , w); add(v , u , w);
		} 
		dfs(1 , 0);
		solve(1 , 0);
		cout << dp[1] << endl;
	}
}