圣诞树彩球

形式化题目

给定一棵 $n$ 个点的树，点权 $a_i \in \{0,1,2\}$ 与正整数 $k$ 。选出尽可能多的两两不相交的连通块，使每个连通块的点权和恰为 $k$ ，输出最大块数。多组数据。

思路

一句话本质：把"区域内存在权和恰为 $k$ 的连通块"改写为"存在权和 $\geqslant k$ 且奇偶性与 $k$ 相同的连通块"（奇偶性由权 1 的点数决定），于是后序遍历中每个节点的未切区域只需维护 $O(1)$ 摘要即可判定"该切了"，每次能切就切整块，贪心达到最优。

先看一个可以直接验证想法的朴素解：

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/**
 * 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-08-28 19:19
 * update_at: 2026-08-28 19:19
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// 每条边是一个"选择对象"：choose[i] = 0 表示不切第 i 条边，1 表示切开。
// 递归先生成完整的 choose[]，到叶子节点再统一检查：
// 切开后树被分成若干连通块，统计权和恰为 k 的连通块个数，更新最优答案。
// 任何"把树切成若干连通块"的方案都唯一对应一组切边选择，因此枚举 2^(n-1) 种
// 选择就枚举了所有方案。适合 n <= 15 的小数据，用于对拍验证 main.cpp。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n, k;
int a[MAXN];                // 点权
int eu[MAXN], ev[MAXN];     // 第 i 条边的两个端点
int choose[MAXN];           // choose[i] = 0/1：第 i 条边 不切/切开
int ans;                    // 最优答案

bool vis[MAXN];

// 检查当前完整 choose[1..n-1] 是否是一组合法切边方案，并统计答案。
void check() {
    // 只保留未切开的边，做连通块扫描
    for (int i = 1; i <= n; i++) vis[i] = false;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        // 用 DFS 找出包含 i 的连通块，累加块内点权和
        int sum = 0;
        stack<int> st;
        st.push(i);
        vis[i] = true;
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            sum += a[u];
            for (int e = 1; e < n; e++) {
                if (choose[e] == 1) continue; // 这条边被切开了
                int v = -1;
                if (eu[e] == u) v = ev[e];
                else if (ev[e] == u) v = eu[e];
                if (v != -1 && !vis[v]) {
                    vis[v] = true;
                    st.push(v);
                }
            }
        }
        if (sum == k) cnt++;
    }
    if (ans < cnt) ans = cnt;
}

// 第 dep 层选择第 dep 条边切 / 不切，dep == n 时所有选择已生成完毕。
void dfs(int dep) {
    if (dep == n) { // 已经决策了 n-1 条边（dep 从 1 到 n-1）
        check();
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int read_int() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    int t = read_int();
    while (t--) {
        n = read_int();
        k = read_int();
        for (int i = 1; i <= n; i++) a[i] = read_int();
        for (int i = 1; i < n; i++) {
            eu[i] = read_int();
            ev[i] = read_int();
        }

        ans = 0;
        dfs(1); // 枚举所有切边选择
        printf("%d\n", ans);
    }
    return 0;
}

这个暴力把问题看成一串 01 选择：choose[i] = 0/1 表示第 i 条边不切 / 切开。递归先生成完整的 choose[]，到叶子节点再统一检查：切开后树分成若干连通块，统计权和恰为 $k$ 的块数。任何"切成连通块"的方案都唯一对应一组切边选择，所以枚举 $2^{n-1}$ 种选择就是枚举所有方案。

这个暴力慢在哪里？

枚举量 $2^{n-1}$ 对 $n = 10^6$ 完全不可行；更本质的是，"一个区域里是否存在权和恰为 $k$ 的连通块"本身是子集搜索，必须找到 $O(1)$ 的判定办法。

树的自底向上有什么确定结构？

后序遍历中，每个节点 $u$ 处理完时，会积累一块"未切部分" $P_u$ ：连通、含 $u$ 。贪心的想法是：一旦 $P_u$ 内存在权和恰为 $k$ 的块就整块切断、计数并清空。于是问题变成两个：(1) 如何 $O(1)$ 判断 $P_u$ 内含这样的块？(2) 为什么"能切就切"不会错过最优解？

$a_i \leqslant 2$ 如何把判定变简单？

关键引理（奇偶性引理）：对 $k > 2$ ，权和为 $k$ 的连通块，先迭代删掉权 0 的叶子（权和不变、仍连通），余块至少有两个正权叶子；若某叶子权 2，删它得到权和 $k-2$ 的块；若叶子全权 1，同时删两个叶子也得 $k-2$ 的块。反复删下去：

存在权和恰为 $k$ 的连通块 ⟺ 存在权和 $\geqslant k$ 且奇偶性与 $k$ 相同的连通块。

奇偶性只由权 1 的点数决定（权 0、2 对奇偶性无贡献）。 $k=1,2$ 时直接验证也成立。这样"找 $k$ 块"就退化成"找权和 $\geqslant k$ 且奇偶匹配的块"。

如何 $O(1)$ 维护这个判定？

维护三个量：sum（未切部分总权和）、cnt[1]（权 1 点数）、mnOne。判定 Check：

若 sum >= k 且 cnt[1] 与 $k$ 奇偶相同：未切部分自身就是候选，由引理存在 $k$ 块。
否则整块奇偶性不匹配，需要"兜底"构造：对每个权 1 的节点 $x$ ，记 $S_x$ 为 $x$ 处理时刻的累计区域和（此刻区域 $Q_x$ 连通、含 $x$ ），mnOne = min S_x。把 $x$ 下方整棵子树拔掉、只留 $x$ ： $E_x = (P \setminus subtree(x)) \cup \{x\}$ 仍是连通块，权和 $= \text{sum} - \text{mnOne} + 1$ 。若它 $\geqslant k$ ： $S_x$ 为偶数时 $E_x$ 奇偶性与 $k$ 匹配； $S_x$ 为奇数时 $P \setminus subtree(x)$ 奇偶性与 $k$ 匹配且权和 $\geqslant k$ （它比 $E_x$ 少 1，不可能等于 $k-1$ 因为奇偶性不同）。两种情况都由引理得到 $k$ 块，所以 sum - mnOne + 1 >= k 可直接判真。（代码里 check() 的实际顺序是先判 sum - mnOne + 1 >= k 再判奇偶匹配，与这里的讲解顺序相反，但两条是"或"关系，完全等价。）

为什么"能切就切"是最优的？

需要证明每次切断没有浪费、也不会堵住后面的块。核心是"下降引理"：若未切区域 $P$ 满足 Check 为假却含权和恰为 $k$ 的块 $B$ ，则 $P$ 内有权 1 的节点 $x \notin B$ ，使 $B \subseteq Q_x$ 且 $Q_x \subsetneq P$ （从 $B$ 的顶端 $w$ 出发取 $P = Q_w$ 时可保证区域严格变小）。直观地说：Check 为假且 $\text{sum}(P) \geqslant k$ ⟹ 整块奇偶性不匹配 ⟹ $P$ 的权 1 点数为奇数，而 $B$ 的权 1 点数 $\equiv k \pmod 2$ ，故 $P \setminus B$ 内必有权 1 点；取 $P \setminus B$ 中 $S_x$ 最小者 $x$ （矛盾论证其实只需 $S_x \geqslant \text{mnOne}$ 与 $x \notin B$ ，任意 $x \in P \setminus B$ 均可）。这样 $x \notin B$ ，于是"若 $B \cap Q_x = \varnothing$ "才可能成立：此时 $Q_x \subseteq P \setminus B$ ， $S_x \leqslant \text{sum}(P) - k$ ，与条件 2 为假（ $\text{mnOne} > \text{sum}(P) - k + 1$ ）矛盾，故 $B \cap Q_x \neq \varnothing$ ；又 $x \notin B$ 且 $B$ 连通——若 $B$ 同时含 $Q_x$ 内外的点， $B$ 内部路径必经 $x$ ，得 $x \in B$ ，矛盾——所以 $B$ 整块落在 $Q_x$ 内。反复应用得到"区域严格变小"的无限序列（节点数递减、权和单调不增），有限节点集上不可能——所以"Check 假 + 含 $k$ 块"不能成立。

由此做交换论证（归纳于树的大小）。设 $C$ 是贪心第一次切断的区域（ $u$ 的整棵子树， $\text{Check}(C)$ 真）。任意最优解 $S$ 的块相对 $C$ 分三类：完全在 $C$ 内、经过 $u$ 越出 $C$ 、完全不碰 $C$ 。逐项排除：

内部块至多一个：若 $C$ 内有两块 $B_1, B_2$ ，设 $z$ 为二者在 $C$ 内的 LCA（ $z$ 未切），由 LCA 性质 $B_1 \cup B_2 \subseteq Q_z$ 、权和 $\geqslant 2k$ ； $\text{Check}(Q_z)$ 必为假——关键前提是 $Q_z$ 未切：若其为真，贪心在 $z$ 或更深处早已切断， $C$ 就不会是第一次切的整棵子树。于是对 $(Q_z, B_1)$ 反复用下降引理得无限严格下降，矛盾。
越出块至多一个：越出块都含 $u$ ，两两相交，至多一块。
内部块与越出块不能并存：设内部块 $B$ 、越出块 $B'$ ， $D' = B' \cap C$ （连通、含 $u$ ）； $B \subseteq C \setminus D'$ ，即 $B$ 落在越出块截断后留下的某个分支里，该分支顶端 $w$ 未切，故 $B \subseteq Q_w$ 且 $\text{Check}(Q_w)$ 为假（真则 $w$ 处早于 $u$ 就该切断），对 $(Q_w, B)$ 反复用下降引理矛盾。

于是 $|S| \leqslant 1 + |S \text{ 中不碰 } C \text{ 的块数}|$ ，这些块在删去 $C$ 后的树 $T \setminus C$ 上仍合法，由归纳 $|S| \leqslant 1 + \text{greedy}(T \setminus C) = \text{greedy}(T)$ 。贪心即最优。

实现上要注意什么？

后序遍历合并 $O(1)$ ；每次 Check 为真就 tmp = Info() 重置并 ans++；多组数据要清空邻接表； $\sum n \leqslant 10^6$ 用快读。

代码

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/**
 * 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-08-28 19:19
 * update_at: 2026-08-28 19:19
 */
// E. Tree（圣诞树彩球）：选出尽可能多的互不相交连通块，使每个连通块点权和恰为 k。
// 100 分解法（官方）：后序遍历贪心，一旦当前"未切连通部分"内含权和恰为 k 的块就整块切断。
//   判断"是否内含"用 Check 引理：等价于存在权和 >= k 且奇偶性与 k 相同的连通块；
//   奇偶性由权值为 1 的点数决定（权值 2 对奇偶性无贡献）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
const int INF = 1e9;

struct Info {
    int cnt[3]; // 当前未切连通部分中权值为 0/1/2 的点数
    int sum;    // 当前未切连通部分的总权和
    int mnOne;  // 部分内所有权值为 1 的节点 x 中，x 处理时刻累计区域和的最小值
    Info() {
        cnt[0] = cnt[1] = cnt[2] = 0;
        sum = 0;
        mnOne = INF;
    }
};

vector<int> g[MAXN]; // 邻接表存树
int c[MAXN];         // 点权 a_i，取值范围 0~2
int n, k;
int ans;             // 已切出的连通块个数

// 合并两个未切部分的信息（mnOne 取两边最小值）。
Info merge_info(const Info& a, const Info& b) {
    Info res;
    res.sum = a.sum + b.sum;
    res.mnOne = min(a.mnOne, b.mnOne);
    for (int i = 0; i < 3; i++) res.cnt[i] = a.cnt[i] + b.cnt[i];
    return res;
}

// 判断当前未切部分 tmp 内是否存在权和恰为 k 的连通块。
// 等价条件（奇偶性引理）：存在权和 >= k 且奇偶性与 k 相同的连通块。
// 1) tmp 整体就满足：sum >= k 且 cnt[1] 奇偶性与 k 相同。
// 2) 否则整块奇偶性不匹配：设 mnOne 取到节点 x（权值 1，处理时刻区域和为 S_x），
//    则 (tmp 去掉 x 下方整棵子树) 与 {x} 的并仍是连通块，权和 = sum - mnOne + 1；
//    若它 >= k 则奇偶性必然匹配（sum 与 k 奇偶相反，S_x 必为偶数时可取 E_x，
//    S_x 为奇数时去掉 x 下方子树的部分奇偶性正好与 k 相同），故由引理断言块存在。
bool check(const Info& tmp) {
    if (tmp.sum < k) return false;
    if (tmp.sum - tmp.mnOne + 1 >= k) return true;
    if (tmp.cnt[1] % 2 == k % 2) return true;
    return false;
}

// 后序遍历：返回以 u 为顶端的"未切连通部分"信息。
// 处理完 u 后若 Check 为真，则整块切断，ans++，并返回空信息。
Info dfs(int u, int p) {
    Info tmp;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == p) continue;
        Info sub = dfs(v, u);
        tmp = merge_info(tmp, sub);
    }
    tmp.cnt[c[u]]++;
    tmp.sum += c[u];
    if (c[u] == 1) {
        // u 是权值为 1 的点：记录此刻（含 u 的）累计区域和
        tmp.mnOne = min(tmp.mnOne, tmp.sum);
    }
    if (check(tmp)) {
        tmp = Info(); // 整块切断并重置
        ans++;
    }
    return tmp;
}

// 快读（数据量总和 1e6，防止 scanf 成为瓶颈）。
int read_int() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    int t = read_int();
    while (t--) {
        n = read_int();
        k = read_int();
        for (int i = 1; i <= n; i++) c[i] = read_int();
        for (int i = 1; i < n; i++) {
            int u = read_int(), v = read_int();
            g[u].push_back(v);
            g[v].push_back(u);
        }

        ans = 0;
        dfs(1, 0);
        printf("%d\n", ans);

        // 多组数据清空邻接表
        for (int i = 1; i <= n; i++) g[i].clear();
    }
    return 0;
}

复杂度

每组数据 $O(n)$ 时间、 $O(n)$ 空间；多组数据总时间 $O(\sum n) \leqslant O(10^6)$ 。

总结

核心转化： $a_i \in \{0,1,2\}$ 使"存在 $k$ 块"等价于"存在权和 $\geqslant k$ 且奇偶匹配的块"（权 1 点数奇偶性），判定降到 $O(1)$ 。
后序贪心 + 整块切断：每个节点只决策一次；正确性由下降引理 + 交换论证保证。
关键实现点：mnOne 是未切部分中所有权 1 节点"处理时刻累计区域和"的最小值，它让整块奇偶不匹配时也能靠"拔掉子树"的构造兜底。
可迁移思想：点权取值很小的"和为定值连通块"问题，优先找奇偶性 / 可减结构（每次减 2），而不是枚举子集；树上的"能切就切"贪心常用"最深区域 + 无限下降"证明最优。

图示解析

这张 ASCII 图展示"模型 → 引理 → 判定 → 贪心 → 答案"的解法路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21树 + 点权 ∈ {0,1,2}，目标：互不相交连通块，每块权和恰为 k
        │
        ▼
后序遍历：每个节点 u 积累"未切区域" P_u（连通，含 u）
        │
        ▼
奇偶性引理：存在 k 块  ⟺  存在权和 ≥ k 且奇偶匹配的块（权1点数奇偶）
        │
        ▼
Check(P)：sum ≥ k 且奇偶匹配？  或   sum - mnOne + 1 ≥ k ？
（mnOne：权1节点"处理时刻区域和"的最小值，拔掉其下方子树仍连通）
        │
        ▼
Check 真 → 整块切断，ans++，区域清空（每个节点只决策一次）
        │
        ▼
下降引理：Check 假则任何 k 块 B 必落入更小区域（区域严格变小：节点数递减、权和单调不增；有限节点集上不可能无限进行）
⇒ 每个最优块都能与贪心的某次切断一一配对（交换论证 + 归纳）
        │
        ▼
答案 ans

从下往上看：判定层保证"切下来的区域里真的有块"（可行性），下降层保证"贪心没漏掉任何最优块"（最优性），两层合起来就是贪心的完整正确性。

目录

形式化题目

思路

代码

复杂度

总结

图示解析