Barn Tree (USACO Silver 2022 December)

Barn Tree (USACO Silver 2022 December)

这个题比较直观，我们用DFS的办法按子树构造出正确的命令序列：dfs()返回子树的净值，如果子树的净值 ≥0\geq 0，则可以在子树内完成所有工作。

  1. 计算每个子树的净正值或净负值（即 ∑ai−m\sum a_i - m）。
  2. 对所有净正的子树进行处理（将多余的部分向上移动）。
  3. 把所有净正的值聚集到子树根节点。
  4. 同样道理，将汇集到根的净正值向下分配到净负值的子树。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
vector<int> adj[200005];
int a[200005];
typedef long long ll;
ll m;      // mean value
 
struct R {
    int src,dst;
    ll v;
};
vector<R> ans;
 
ll net[200005];
 
// push net balance all the way up
ll dfs(int s, int e) {
    ll total = a[s]-m;
 
    for (int v: adj[s]) {
        if (v == e) continue;
        ll r = dfs(v, s);
        total += r;
        if (r > 0)
            ans.push_back({v,s,r});
    }
    net[s] = total;
    return total;
}
 
// push balance down to all deficiet nodes
void down(int s, int e) {
    for (int v: adj[s]) {
        if (v == e) continue;
        if (net[v] < 0)
            ans.push_back({s,v,-net[v]});
        down(v, s);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        m += a[i];
    }
    m /= n;
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    dfs(1, 0);
    down(1, 0);
 
    printf("%d\n", ans.size());
    for (R r: ans)
        printf("%d %d %lld\n", r.src, r.dst, r.v);
 
    return 0;
}