8307 【暑假提高组模拟冲刺赛#5T4】奇偶树做题随笔题解-171主机测评

8307 【暑假提高组模拟冲刺赛#5T4】奇偶树做题随笔/题解

文章目录

8307 【暑假提高组模拟冲刺赛#5T4】奇偶树做题随笔/题解
- 题意简述
- 赛时想法
- 正解
- - 1. 关键观察
  - 2. 维护 `mn`
  - 3. 判断能否切掉
  - 4. 贪心正确性证明
  - 5. 复杂度
- 参考代码
- 总结回顾
- 易错点与调试心得（血泪汇总）
- - 1. ⚠️ `mn` 的初始值和更新
  - 2. ⚠️ 叶子节点的处理
  - 3. ⚠️ 切掉后返回空块
  - 4. ⚠️ 多组数据清空邻接表
  - 5. ⚠️ 差值奇偶判断
  - 6. ⚠️ 使用 `long long`

题意简述

给你一棵包含

$n$ 个节点的树，每个节点

$i$ 有一个权值

(

∈

{

}

)

a_i (a_i\\in\\{0,1,2\\})

$a_{i} (a_{i} \in {0, 1, 2})$ ，现可以断开任意条边使之成为一个森林。问权值和恰好为

(

≤

)

k (1\\le k\\le1e6)

$k (1 \leq k \leq 1 e 6)$ 的连通块数量最多能有多少。共有

$T$ 组测试数据,保证

∑

≤

\\sum_{i=1}^{T}n_i\\le1e6

$\sum_{i = 1}^{T} n_{i} \leq 1 e 6$ 。

赛时想法

由于是T4，为了前面的暴力，这题就放了，想想还是有些可惜。

正解

浅层思考时不能被"断开边"迷惑，不然后续敲代码会很麻烦。转化成：树上的子树的权值和就好想了。

我们可以发现点权的范围很有意思：

或

0,1或2

$0, 1 或 2$ 。事实上有贡献的只有权值为

$1$ 和

$2$ ，那我们先看看树形DP有没有前途：答案是没有，因为如果用类似”树上背包“的思路

$n$ 和

$k$ 都可能开到

1e6

$1 e 6$ ，直接MLE。

所以让我们换一种清奇的思路：

这道题的核心在于权值只有 0、1、2 带来的奇偶性规律，以及自底向上的贪心。

1. 关键观察

对于一个连通块（残余块），假设它的权值和为

$S$ 。如果

≥

S \\ge k

$S \geq k$ ，且

−

S – k

$S - k$ 是偶数，那么一定能通过删掉一些叶子（权值为 2 的叶子，或两个权值为 1 的叶子）将权值和降为

$k$ 。因为每次操作可以让总和减少 2，并且始终存在这样的叶子（只要块内点数足够，且叶子权值不为 0，0 可以直接删掉不影响总和）。

若

−

S – k

$S - k$ 是奇数，则我们需要先删掉一个奇数权值的子块（权值和为奇数），使得剩余差值变为偶数。为了保留尽可能多的权值，我们应该删掉最小的奇数子块。

因此，每个残余块只需要记录两个信息：

sum：当前残余块的权值和。
mn：该残余块内部所有可被单独切除的奇数权值子块的最小权值和。

2. 维护 mn

在 DFS 合并儿子时，mn 取所有儿子的 mn 的最小值。
加上当前节点自己的权值后，如果整个残余块的总和 sum 变成了奇数，则整个块也可以作为一个奇数子块，用 sum 更新 mn。

3. 判断能否切掉

对于一个残余块（当前节点处理完后），如果：

sum < k：无法切，原样返回给父节点。
sum >= k：
- 若 (sum – k) % 2 == 0：直接切掉，答案 +1，返回空块（sum=0, mn=INF）。
- 否则（差为奇数）：
  - 若存在奇数子块（mn != INF）且 sum – mn >= k：切掉最小奇数子块后，剩余部分仍可凑出 k，因此也能切。答案 +1，返回空块。
  - 否则，不能切，返回给父节点。

4. 贪心正确性证明

“能切就切”一定不劣于“留给父节点”。

假设当前残余块已经满足切割条件（即可以凑出 k），如果我们不切它，而是把它上交给父节点，那么它最多也只能成为父节点的一部分，最终至多贡献 1 个合法块（与父节点合并后可能还是 1 个，或者更少）。但如果现在就切掉，它马上贡献 1 个，并且父节点得到的是空块，不影响父节点继续切割其他部分。所以“早切”不会减少答案，反而可能让父节点更轻，更容易切出其他块。因此贪心策略正确。

5. 复杂度

每个节点只访问一次，合并儿子和判断都是 O(1)，所以单组数据复杂度

(

)

O(n)

$O (n)$ ，总复杂度

(

∑

)

O(\\sum n)

$O (\sum n)$ ，完美通过。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int INF = 4e6 + 5; // 大于最大可能权值和 2e6

int n, k, ans;
int a[N];
vector<int> g[N];

pair<int,int> dfs(int u, int prt) {
pair<int,int> cur = {0, INF}; // sum, mn

for (int v : g[u]) {
if (v == prt) continue;
auto son = dfs(v, u);
cur.first += son.first;
cur.second = min(cur.second, son.second);
}

cur.first += a[u];
if (cur.first & 1) { // 当前整个块是奇数，更新 mn
cur.second = min(cur.second, cur.first);
}

if (cur.first >= k) {
int diff = cur.first – k;
if (diff % 2 == 0) {
ans++;
return {0, INF};
} else {
if (cur.second != INF && cur.first – cur.second >= k) {
ans++;
return {0, INF};
}
}
}
return cur;
}

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

int T;
cin >> T;
while (T—) {
ans = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
g[i].clear();
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
cout << ans << '\\n';
}
return 0;
}

总结回顾

本题的核心是利用权值只有 0/1/2 的性质，将问题简化为只关心奇偶性和最小奇数块。
状态设计极其精简：每个节点只需返回两个整数（sum 和 mn），完全无需存储 DP 数组。
贪心策略“能切就切”通过反证法证明正确。
时间复杂度 $10^6 106 的数据范围。$

易错点与调试心得（血泪汇总）

1. ⚠️ mn 的初始值和更新

mn 必须初始化为足够大的数（如 INF = 4e6+5），大于任何可能的权值和（最大 $\\times 10^6 2×106）。$
合并儿子时：cur.second = min(cur.second, son.second); 不要加任何奇偶判断，直接取最小。
加入自身后，若 cur.first 为奇数，必须用 cur.first 更新 mn。

2. ⚠️ 叶子节点的处理

不要单独处理叶子，让所有节点统一走“合并儿子 → 加自身 → 判断切分”的流程，叶子自然正确（儿子循环为空）。

3. ⚠️ 切掉后返回空块

切掉后必须返回 {0, INF}，表示该节点对父节点无贡献（权值和为 0，且无奇数子块）。如果忘记清零，父节点会错误地继承已切掉部分的权值，导致答案偏大。

4. ⚠️ 多组数据清空邻接表

每组测试数据前，必须清空所有节点的邻接表 g[i].clear()，否则残留边会导致 DFS 遍历错误。

5. ⚠️ 差值奇偶判断

差值为偶数时直接切；为奇数时，必须检查 cur.second != INF（即存在奇数块），并且 cur.first – cur.second >= k。少任何一个条件都会 WA。

6. ⚠️ 使用 long long

虽然权值和最大只有 $\\times 10^6 2×106，但为了安全，建议使用 long long 或 int 足够（INF 要大于 2e6）。$

通过这道题，我们深刻体会到：当数据范围极大时，必须放弃枚举状态的 DP，转而寻找问题的数学本质。权值只有 0/1/2 的陷阱，正是出题人精心设计的突破口。 ng long`

虽然权值和最大只有 $\\times 10^6 2×106，但为了安全，建议使用 long long 或 int 足够（INF 要大于 2e6）。$

通过这道题，我们深刻体会到：当数据范围极大时，必须放弃枚举状态的 DP，转而寻找问题的数学本质。权值只有 0/1/2 的陷阱，正是出题人精心设计的突破口。

8307 【暑假提高组模拟冲刺赛#5T4】奇偶树做题随笔题解