牛客训练赛9补题记录

J: The Escape Plan of Groundhog

做法：枚举上下两条边界，接着从左往右做前缀和！

理论AC

B: Groundhog and Apple Tree

显然影响答案的只有遍历子节点的顺序。

对于子节点$x,y$，

• 如果访问后血量都增加（$delta[x]>0,delta[y]>0$），则先访问需求（$need[i]$）较小的
• 如果访问后血量都减少，则需要考虑不同顺序时需要的血量
  • 先访问$x$，则所需血量为$need[x]+\min(0,need[y]-(need[x]+delta[x]))$
  • 先访问$y$，则所需血量为$need[y]+\min(0,need[x]-(need[y]+delta[y]))$
• 否则，先访问加血的节点，再访问扣血的节点

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<ll, ll>
#define sqr(x) ((x)*(x))
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 100;

ll apple[maxn];
ll n;
vector<pii> G[maxn];
ll need[maxn], delta[maxn];

void dfs(int u, int fa){
    need[u] = 0;
    for(pii & e:G[u]){
        if(e.first == fa) continue;
        dfs(e.first, u);
        delta[e.first] -= 2 * e.second;
        need[e.first] += e.second;
        if(need[e.first] < -delta[e.first]){
            need[e.first] = -delta[e.first];
        }
    }

    sort(G[u].begin(), G[u].end(), [&](pii a, pii b){
        int x = a.first, y = b.first;
        if(delta[x] >= 0 && delta[y] >= 0) return need[x] < need[y];
        if(delta[x] < 0 && delta[y] < 0){
            return need[x] + max(0ll, need[y] - (need[x] + delta[x])) <
                   need[y] + max(0ll, need[x] - (need[y] + delta[y]));
        }
        return delta[x] > delta[y];
    });

    ll cur = delta[u] = apple[u];
    for(pii e:G[u]){
        int v = e.first;
        if(v == fa) continue;
        if(cur < need[v]) {
            need[u] += need[v] - cur;
            cur = need[v];
        }
        cur += delta[v];
        delta[u] += delta[v];
        if(cur < 0) {
            need[u] += -cur;
            cur = 0;
        }
    }
    need[u] = max(need[u], -delta[u]);
}

void solve(){
    cin >> n;
    for(int i=0; i<=n; i++) G[i].clear();
    for(int i=1; i<=n; i++) cin >> apple[i];
    for(int i=1, u, v, w; i<n; i++){
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dfs(1, 0);
    cout << need[1] << '\n';
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--)
    solve();
}