Color a tree

形式化题目

给定一棵以 $R$ 为根的有根树，点 $i$ 有权值 $A_i$ 。要给所有点各染一次色，染色的次序必须满足：

根 $R$ 随时可染；
除根外，点 $i$ 被染色之前，它的父亲 $\mathrm{fa}(i)$ 必须已经染过色，即 $\mathrm{time}(\mathrm{fa}(i)) < \mathrm{time}(i)$ 。

若点 $i$ 是第 $T$ 个被染色的点，代价为 $T \cdot A_i$ 。要求给出一个合法的染色次序，使总代价

\sum_{i=1}^{n} \mathrm{time}(i)\cdot A_i

最小。

原题把权值直接叫「权值」，下文沿用。

暴力解法

思路

$n \leqslant 1000$ 时全排列不可能，但小规模可以做：直接按「每一步从所有父亲已染色的未染点中挑一个」做搜索，枚举全部合法染色次序取最小代价。

每次在 $n$ 个点里扫一遍找可染点，深度 $n$ ，总复杂度 $O(n!)$ 量级，只够跑 $n \leqslant 9$ 的对拍。

代码

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/**
 * 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-11-10 09:55
 * update_at: 2026-11-10 09:55
 */
// brute.cpp：小数据暴力解，枚举所有满足「父亲先染色」的染色顺序，取最小代价。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 12;

int n, root;
ll  w[maxn];
int fa[maxn];
bool used[maxn];      // 是否已染色
ll  best;

void dfs(int dep, ll cost) {
    if (dep > n) {
        best = min(best, cost);
        return;
    }
    for (int i = 1; i <= n; i ++ ) {
        if (used[i]) continue;
        if (i != root && !used[fa[i]]) continue;   // 父亲必须先染色
        used[i] = true;
        dfs(dep + 1, cost + (ll)dep * w[i]);
        used[i] = false;
    }
}

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

    while (cin >> n >> root) {
        if (n == 0 && root == 0) break;
        for (int i = 1; i <= n; i ++ ) cin >> w[i], used[i] = false;
        for (int i = 1, a, b; i < n; i ++ ) {
            cin >> a >> b;
            fa[b] = a;
        }
        best = LLONG_MAX;
        dfs(1, 0);
        cout << best << '\n';
    }
    return 0;
}

复杂度

时间 $O(n!)$ ，空间 $O(n)$ 。只能验证小数据。

瓶颈

搜索把「选谁」和「约束」混在一棵巨大的搜索树里， $1000$ 个点完全跑不动。要快，必须从结构上直接定出最优次序，而不是枚举。

正解

思路

先看没有「父亲先染」限制的版本：每轮可任意选点，那就是把 $A_i$ 从大到小排序后依次染色，即排序不等式的结论。

关键性质：加上限制后，权值最大的那个（非根的）点 $x$ ，一旦它的父亲 $f$ 被染色，下一个必然染 $x$ 。因为此时可染点里 $x$ 权值最大，任何把它往后挪的交换都会让答案变大。于是 $f$ 与 $x$ 的染色是相邻的。

合并与等效权值：既然必须相邻，就可以把 $f$ 和 $x$ 合并为一个「点集合」。设有两个块 $A$ （点数 $s_A$ ，点权和 $w_A$ ）与 $B$ （点数 $s_B$ ，点权和 $w_B$ ）：

若顺序为 $A \to B$ ：块 $B$ 内每个点相对于自身内部排位被延后了 $s_A$ 个时刻，产生额外代价 $s_A \cdot w_B$ ；
若顺序为 $B \to A$ ：块 $A$ 内每个点被延后 $s_B$ 个时刻，产生额外代价 $s_B \cdot w_A$ 。

先排 $A$ 优于先排 $B \iff s_A \cdot w_B < s_B \cdot w_A \iff \frac{w_A}{s_A} > \frac{w_B}{s_B}$ 。即两个块之间的先后顺序完全由平均权值 $\frac{w}{s}$ 决定！比较时可直接十字相乘（ $w_A \cdot s_B > w_B \cdot s_A$ ），无需使用浮点数。

代价计算：贡献法动态累加（无需带权并查集）：许多题解会用带权并查集去维护每个点的绝对染色时刻，最后再统一求和，这把问题不必要地复杂化了。实际上可以直接用贡献法在合并时动态结算代价：

初始基准代价：假设所有点都在第 1 个时刻染色，基准总代价为：
$\text{ans} = \sum_{i=1}^{n} A_i$
合并时的延后增量：每一步挑选当前平均权值最大的非根块 $u$ ，将其绑定在其父节点所在的块 $f$ 之后。这意味着块 $u$ 内的所有点在时序上都被整整推迟了 $s_f$ 个时刻，因此对总答案产生的确切增量就是：
$\Delta = s_f \times w_u$
我们只需在合并时直接累加：
$\text{ans} \leftarrow \text{ans} + s_f \times w_u$
并查集维护：仅需最普通的并查集维护连通块代表元即可（无需维护任何边权）：
$p[u] = f,\quad s_f \leftarrow s_f + s_u,\quad w_f \leftarrow w_f + w_u$

进行 $n-1$ 次贪心合并后，所有点全部并入根节点所在连通块，此时的 $\text{ans}$ 即为最终最小总代价。

用样例（ $n=5$ ，根为 $1$ ， $A=[1,2,1,2,4]$ ，边为 $1\!-\!2,1\!-\!3,2\!-\!4,3\!-\!5$ ）走一遍合并过程（初始 $\text{ans} = 1+2+1+2+4 = 10$ ）：

步	当前最大平均权值的非根块 $u$	并入父块 $f$	产生代价增量 $\Delta = s_f \times w_u$	累计代价 $\text{ans}$	合并后新块信息 $(s, w)$
1	$\{5\}\ (s=1, w=4)$	$\{3\}\ (s=1, w=1)$	$1 \times 4 = 4$	$10 + 4 = 14$	$\{3, 5\}\ (s=2, w=5)$ ，均值 $2.5$
2	$\{3, 5\}\ (s=2, w=5)$	$\{1\}\ (s=1, w=1)$	$1 \times 5 = 5$	$14 + 5 = 19$	$\{1, 3, 5\}\ (s=3, w=6)$ ，均值 $2.0$
3	$\{2\}\ (s=1, w=2)$	$\{1, 3, 5\}\ (s=3, w=6)$	$3 \times 2 = 6$	$19 + 6 = 25$	$\{1, 3, 5, 2\}\ (s=4, w=8)$ ，均值 $2.0$
4	$\{4\}\ (s=1, w=2)$	$\{1, 3, 5, 2\}\ (s=4, w=8)$	$4 \times 2 = 8$	$25 + 8 = 33$	全树合并完毕

最终答案为 $33$ ，与样例完全一致。每一步增量的物理意义极为清晰，无需任何回溯。

代码

同一算法的 C++ 与 Python 实现，逻辑一致。

C++ 版本：

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/**
 * 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-11-10 09:55
 * update_at: 2026-11-10 12:10
 */
// MTREECOL - Color a tree
// 贪心：每次挑选等效权值（平均值）最大的非根块，并入其父节点所在的块；
// 贡献法：块 u 接在父块 f 后面时，u 内所有点整体延后 siz[f] 个时刻，代价增量为 siz[f] * w[u]。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

int n, root;
ll  w[MAXN];    // 连通块当前的总点权和
int siz[MAXN];  // 连通块当前包含的点数
int fa[MAXN];   // 原树上每个点的父节点
int p[MAXN];    // 普通并查集：定位每个点所属的连通块代表元

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

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

    while (cin >> n >> root && (n || root)) {
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> w[i];
            ans += w[i]; // 初始基准代价：假定所有点都在第 1 个时刻染色
            siz[i] = 1;
            p[i] = i;
        }

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

        // 不断将当前平均权值最大的非根块并入其父块，共合并 n - 1 次
        for (int step = 1; step < n; step++) {
            int u = -1;
            for (int i = 1; i <= n; i++) {
                if (i == root || find(i) != i) continue;
                // 十字相乘比较平均值：w[i]/siz[i] > w[u]/siz[u]
                if (u == -1 || w[i] * siz[u] > w[u] * siz[i]) {
                    u = i;
                }
            }

            int f = find(fa[u]);
            // 物理意义：块 u 紧随块 f 染色，u 内所有点被延后 siz[f] 个时刻
            ans += (ll)siz[f] * w[u];

            // 并查集合并
            p[u] = f;
            siz[f] += siz[u];
            w[f] += w[u];
        }

        cout << ans << "\n";
    }

    return 0;
}

Python 版本：

python

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#!/usr/bin/env python3
# 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-11-10 12:15
# update_at: 2026-11-10 12:15

import sys


def solve_case(n: int, root: int, w: list[int], edges: list[tuple[int, int]]) -> int:
    """求树上染色的最小代价（平均权值贪心 + 贡献法延后增量）。"""
    fa = [0] * (n + 1)
    for u, v in edges:
        fa[v] = u

    p = list(range(n + 1))

    def find(x: int) -> int:
        if p[x] != x:
            p[x] = find(p[x])
        return p[x]

    weight = [0] + w
    siz = [1] * (n + 1)
    ans = sum(w)

    for _ in range(n - 1):
        # 挑选平均值最大的非根代表元
        best_u = -1
        for i in range(1, n + 1):
            if i == root or find(i) != i:
                continue
            if best_u == -1 or weight[i] * siz[best_u] > weight[best_u] * siz[i]:
                best_u = i

        f = find(fa[best_u])
        ans += siz[f] * weight[best_u]

        # 并查集合并
        p[best_u] = f
        siz[f] += siz[best_u]
        weight[f] += weight[best_u]

    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []

    while True:
        token = next(data, None)
        if token is None:
            break
        n = int(token)
        root = int(next(data))
        if n == 0 and root == 0:
            break

        w = [int(next(data)) for _ in range(n)]
        edges = [(int(next(data)), int(next(data))) for _ in range(n - 1)]

        out.append(str(solve_case(n, root, w, edges)))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

共进行 $n - 1$ 次合并，每轮线性扫描 $O(n)$ 寻找最大平均权值块，普通并查集操作近乎 $O(1)$ 。总时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

总结

等效权值：加上“先染父亲”约束后，最大权值块必然紧随父亲染色，两者可捆绑合并，用平均权值作为等效权值统一排序；
贡献法结算：合并块 $u$ 到父块 $f$ 后面时，块 $u$ 的所有元素整体延后 $s_f$ 个时刻，代价增量天然就是 $s_f \times w_u$ ；
极简实现：无需带权并查集、无需记录具体染色序列、无需浮点数，普通并查集 + 整数十字相乘即可优雅求解。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结