Barn Tree

题意

有一棵 $N$ 个点的树，第 $i$ 个点有 $h_i$ 个草捆。每次操作可以沿一条边，把某个正整数数量的草捆从一个端点移动到另一个端点。

要求用尽可能少的操作，让所有点的草捆数量相同，并输出任意一种最优操作序列。

思路

先看一个小数据递归写法。它直接按官方解析的 distribute 思路处理子树，更适合理解操作顺序。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:17
 * update_at: 2026-07-11 19:20
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;

struct Operation {
    int from, to;
    ll val;
};

int n;
ll h[MAXN], avg, sub[MAXN];
vector<int> g[MAXN];
vector<Operation> ans;

void dfs_sum(int u, int fa) {
    sub[u] = h[u] - avg;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;
        dfs_sum(v, u);
        sub[u] += sub[v];
    }
}

// 小数据递归版，直接对应官方 distribute 思路。
void dfs_build(int u, int fa) {
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa || sub[v] < 0) continue;
        dfs_build(v, u);
        if (sub[v] > 0) {
            ans.push_back((Operation){v, u, sub[v]});
        }
    }

    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa || sub[v] >= 0) continue;
        ans.push_back((Operation){u, v, -sub[v]});
        dfs_build(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        avg += h[i];
    }
    avg /= n;

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_sum(1, 0);
    dfs_build(1, 0);

    cout << ans.size() << '\n';
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i].from << ' ' << ans[i].to << ' ' << ans[i].val << '\n';
    }

    return 0;
}

最终每个点都要变成平均值 avg。为了看清楚每个子树多了还是少了多少，先把每个点改成：

text

1h[i] = h[i] - avg

现在目标就是让所有点都变成 0。

如果删掉一条边，某一侧子树的和不是 0，那么这条边一定要运输草捆；否则这侧多出来或缺少的草捆无法跨出去平衡。所以最少操作数至少是“子树和非零的边数”。

官方构造可以达到这个下界。把树任意定根，令：

text

1sub[x] = x 子树内所有 h[i]-avg 的和

对父亲 u 的一个儿子 v：

如果 sub[v] > 0，说明 v 子树多了 sub[v] 个草捆，最后要从 v 运到 u。
如果 sub[v] < 0，说明 v 子树缺少 -sub[v] 个草捆，最后要从 u 运到 v。
如果 sub[v] = 0，这条边不需要使用。

操作顺序也很重要：

对 sub[v] > 0 的儿子，先处理完儿子子树，再把多余草捆从 v 运到 u；
对 sub[v] < 0 的儿子，先把缺少的草捆从 u 运到 v，再处理儿子子树。

这样可以保证每次从某个点移出草捆时，那个点手里确实有足够的草捆。

主程序为了避免链状树递归爆栈，先用迭代栈求父亲和遍历顺序，再用另一个栈模拟上面的递归操作顺序。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:17
 * update_at: 2026-07-11 19:20
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005;

struct Operation {
    int from, to;
    ll val;
};

struct Action {
    int type; // 0 表示处理一个节点，1 表示输出一条操作
    int u, v;
    ll val;
};

int n;
ll h[MAXN], avg, sub[MAXN];
int parent_node[MAXN];
vector<int> g[MAXN];
vector<int> order;
vector<Operation> ans;

void build_parent() {
    vector<int> st;
    st.push_back(1);
    parent_node[1] = 0;

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_node[u]) continue;
            parent_node[v] = u;
            st.push_back(v);
        }
    }
}

void calc_subtree_sum() {
    for (int i = 1; i <= n; i++) {
        sub[i] = h[i] - avg;
    }

    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        if (parent_node[u] != 0) {
            sub[parent_node[u]] += sub[u];
        }
    }
}

void build_operations() {
    vector<Action> st;
    st.push_back((Action){0, 1, 0, 0});

    while (!st.empty()) {
        Action cur = st.back();
        st.pop_back();

        if (cur.type == 1) {
            ans.push_back((Operation){cur.u, cur.v, cur.val});
            continue;
        }

        int u = cur.u;

        // 负子树：先从父亲给子树，再处理子树。由于栈是后进先出，这里倒序压栈。
        for (int i = (int)g[u].size() - 1; i >= 0; i--) {
            int v = g[u][i];
            if (v == parent_node[u] || sub[v] >= 0) continue;
            st.push_back((Action){0, v, 0, 0});
            st.push_back((Action){1, u, v, -sub[v]});
        }

        // 正子树：先处理子树，再把多余草捆交给父亲。
        for (int i = (int)g[u].size() - 1; i >= 0; i--) {
            int v = g[u][i];
            if (v == parent_node[u] || sub[v] < 0) continue;
            if (sub[v] > 0) {
                st.push_back((Action){1, v, u, sub[v]});
            }
            st.push_back((Action){0, v, 0, 0});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        avg += h[i];
    }
    avg /= n;

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build_parent();
    calc_subtree_sum();
    build_operations();

    cout << ans.size() << '\n';
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i].from << ' ' << ans[i].to << ' ' << ans[i].val << '\n';
    }

    return 0;
}

复杂度

每条边只被遍历常数次，每条需要运输的边只输出一次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是从“每个点到平均值的差”出发，观察每条边分开的子树总和。

子树和非零的边必须用一次，而按正子树后交、负子树先给的 DFS 顺序，就能用正好这些操作完成平衡。

目录

题意

思路

代码

复杂度

总结