n ≤ 1000,以每个结点为起点 DFS 一遍,O(n²) 枚举全部简单路径。
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n,每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点 s 和节点 t,并从节点 s 出发移动到节点 t,移动过程中小杨不能够经过重复节点。
小杨希望自己在至多经过 k 个黑色节点的前提下,经过的总节点数尽可能多,请你帮小杨选择经过最多的节点数是多少。
| 样例 | 内容 |
|---|---|
| 输入 #1 | 5 1 |
| 输出 #1 | 3 |
n ≤ 1000,所有路径的数量级是 O(n²) = 10⁶,完全在 1 秒的承受范围内。dep(路径上有几个点)和 blk(其中几个是黑的),只要 blk ≤ k 就用 dep 去更新答案;一旦 blk > k 就立即停止深入(再往下只会更多黑点)。树简单路径不重复结点黑点计数O(n²) 暴力枚举搜索剪枝
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, k;第二行 n 个颜色值;随后 n − 1 行边 uᵢ, vᵢ |
| 输出 | 一个整数:在满足黑点数 ≤ k 的路径中,最多的结点数 |
| 数据范围 | 1 ≤ n ≤ 1000,0 ≤ k ≤ 1000 |
| 颜色 | aᵢ = 0 表示白,aᵢ = 1 表示黑 |
| 子任务 1 | 20%:n ≤ 100,k ≤ 100,树的形态是一条链 |
| 子任务 2 | 20%:n ≤ 1000,k = 0 |
| 子任务 3 | 60%:n ≤ 1000,k ≤ 1000 |
O(n²) 够用?枚举 (s, t) 有 n² 种,n ≤ 1000 时约 10⁶;而"以每个 s 为起点做一次 DFS"正好把从 s 出发的所有路径一次走完,复杂度同样是 O(n²),远远安全blk > k 可以立刻剪枝?从当前结点再往下走,路径只会变长、黑点数只会增加或不变,绝不可能"越走黑点越少";所以一旦超过 k,这条分支的所有后继都不可能合法dep = 1、blk = col[s];漏掉起点是本题最常见的错误颜色:1 = 白、2 = 白、3 = 黑、4 = 黑、5 = 黑;边:1—2、2—3、2—5、1—4。
| 结点 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 颜色 | 白 | 白 | 黑 | 黑 | 黑 |
这棵树长这样:3 和 5 挂在 2 下面,4 挂在 1 下面,1—2 是主干。因为 k = 1,路径上最多只能出现一个黑点。
| 路径 | 经过的结点 | 黑点数 | 结点数 | 是否可行 |
|---|---|---|---|---|
| 3 → 2 → 1 | 3、2、1 | 1(只有 3) | 3 | ✅ 可行,最优 |
| 4 → 1 → 2 | 4、1、2 | 1(只有 4) | 3 | ✅ 可行,同样最优 |
| 4 → 1 → 2 → 3 | 4、1、2、3 | 2(4 和 3) | 4 | ❌ 黑点 2 > k = 1 |
| 3 → 2 → 5 | 3、2、5 | 2(3 和 5) | 3 | ❌ 黑点 2 > k = 1 |
| 5 → 2 → 1 → 4 | 5、2、1、4 | 2(5 和 4) | 4 | ❌ 黑点 2 > k = 1 |
| 4 → 1 → 2 → 3(换起点试) | 4、1、2、3 | 2 | 4 | ❌ 超过 k |
| 只走一个白点,如 1 | 1 | 0 | 1 | ✅ 可行但不是最优 |
起点 3 是黑的:dep = 1、blk = 1(还没超限)
走到 2(白):dep = 2、blk = 1 ✅ 更新 best = 2
走到 1(白):dep = 3、blk = 1 ✅ 更新 best = 3
再走到 4(黑):dep = 4、blk = 2 > k,剪枝
回到 2 走 5(黑):dep = 3、blk = 2 > k,剪枝
起点 3 得到最优值 3
起点 4 是黑的:dep = 1、blk = 1
走到 1(白):dep = 2、blk = 1
走到 2(白):dep = 3、blk = 1 ✅ 与当前最优持平
再走到 3 或 5 都是黑:blk 会变成 2,剪枝
起点 4 也得 3
起点 5:5 → 2 → 1 也是 3,再往前就超限
起点 1:1 → 2 → 3 是 3;1 → 2 → 5 也是 3
起点 2:2 → 1 → 4 是 3,2 → 3 只有 2
没有任何路径能到 4 个点还不超 k
✅ 全局最优 = 3
3 → 2 → 1 或 4 → 1 → 2。k 就合法。把样例的 k 从 1 改成 2,再算一遍,你会看到弯路的威力:
| 路径 | 经过的结点 | 黑点数 | 结点数 | 是否可行 |
|---|---|---|---|---|
| 3 → 2 → 1 → 4 | 3、2、1、4 | 2(3 和 4) | 4 | ✅ 可行,最优 |
| 5 → 2 → 1 → 4 | 5、2、1、4 | 2(5 和 4) | 4 | ✅ 同样最优 |
| 3 → 2 → 5 | 3、2、5 | 2 | 3 | ✅ 可行但不是最优 |
路径依次经过 3(黑)、2(白)、1(白)、4(黑)
黑点共 2 个,恰好等于 k = 2,没有超限
结点数 = 4,比任何一条"直链"都长
它在结点 2 与 1 之间"拐了个弯",穿过了主干
✅ k = 2 时答案变成 4
树上的最长直链是 3 → 2 → 1 → 4?
其实这条路本身就是一条路径,但如果只沿着"某条一直往下的链"找
就会得到 2 → 1 → 4(3 个点)或 3 → 2 → 1(3 个点)
漏掉"两个分支接起来"的那条
❌ 只算直链会漏解
n ≤ 1000 这个范围给出的暗示:出题人允许你用 O(n²)。以 s 为根向下走,携带 dep 与 blk,超限就剪枝,合法就更新答案
n ≤ 1000 时 n² = 10⁶,C++ 几毫秒就能跑完,既然暴力够快,就没有理由去写更容易出错的复杂算法。dp[u][j] 表示从 u 向下、黑点数为 j 的最长链长度,再合并两条子树链
n 放大到 2 × 10⁵ 时,O(n²) 就废了,而 O(nk) 的树形 DP 还能撑住(前提是 k 不大)。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 每个起点各跑一次 DFS | O(n²) ≈ 10⁶ | ✅ 推荐(本题最稳) |
| 树形 DP 分层合并 | O(n k) | ✅ 可行,代码更绕 |
| 只求"树上最长直链" | O(n) | ❌ 会漏掉拐弯路径,答案偏小 |
第一行输入 n k,第二行输入 n 个颜色(0 白 1 黑),随后 n − 1 行输入一条边。程序会以每个结点为起点 DFS,展示每个起点的最优值、全局答案与一条最优路径。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int n, k; int col[1005]; // col[i] = 0 白,1 黑 vector<int> g[1005]; int best = 0; // 目前找到的最多结点数 // 从 u 往下走:fa 防止走回父亲,dep = 路径上的结点数,blk = 路径上的黑点数 void dfs(int u, int fa, int dep, int blk) { if (blk > k) return; // 黑点已经超限,这条分支全部作废 if (dep > best) best = dep; // 这是一条合法路径,用它更新答案 for (int i = 0; i < (int)g[u].size(); i++) { int v = g[u][i]; if (v == fa) continue; // 不回头(树上"不重复结点"就靠这一行保证) dfs(v, u, dep + 1, blk + col[v]); } } int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &col[i]); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } // 每个结点都当一次起点,覆盖所有可能的 (s, t) 组合 for (int s = 1; s <= n; s++) dfs(s, 0, 1, col[s]); // 路径一定包含起点:dep = 1,黑点数先算上 col[s] printf("%d\n", best); return 0; }
dep = 1, blk = col[s]);② if (v == fa) continue; 保证了"不走回头路",等价于"不经过重复结点";③ 剪枝放在最前面,blk > k 时不再深入,也不更新答案。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dfs(s, 0, 1, col[s]); | 起点初始化 | 路径包含起点,所以结点数从 1 起、黑点数先加 col[s] |
if (blk > k) return; | 剪枝 | 再往下走黑点只会更多,超限就没有翻盘的可能 |
if (dep > best) best = dep; | 更新答案 | 能执行到这一行,说明 blk ≤ k 合法 |
if (v == fa) continue; | 不走回头路 | 树中"不经过重复结点" ⟺ 只沿父亲以外的方向走 |
dfs(v, u, dep + 1, blk + col[v]); | 向下扩展 | 结点数 +1,黑点数加上新结点的颜色 |
for (int s = 1; s <= n; s++) | 枚举起点 | n 次 DFS × 每次 O(n) = O(n²) |
best(超限路径绝不算合法);③ 只算"一条直链"——路径可以拐弯,必须让每个点都当起点;④ 把树读成了有向图(无向边两个方向都要加,否则走不通);⑤ 递归层数:n ≤ 1000 时最深 1000 层,C++ 默认栈足够,不用改。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 1 | 3 | 题面样例:3 → 2 → 1 或 4 → 1 → 2,3 个点 1 个黑点 |
5 2 | 4 | k 变大后"拐弯路径" 3 → 2 → 1 → 4 成为最优 |
4 0 | 4 | k = 0 且全白:整条链 4 个点都能走 |
3 1000 | 3 | 全黑但 k 足够大:整条链都能走 |
4 1 | 2 | 白心菊花,k = 1:走两个黑叶子会变 2 个黑点,只能走"白心 + 一个黑叶" |
2 0 | 1 | k = 0:只能选那个白点自己 |
1 0 | 1 | n = 1 没有边,单个白点合法 |
5 1 | 3 | 黑白交替链:3 → 2 → 1 是 3 个点 1 个黑点 |
blk > k 剪枝了吗?④ 无向边两个方向都加了吗?dep = 1、blk = col[s]。blk > k 的路径一律不合法,必须放在最前面剪掉。n 个起点,每个起点各跑一次 DFSO(n)O(n²),n = 1000 时约 10⁶ 次操作邻接表 vector<int> g[n + 1] 存 2(n − 1) 条弧,加上颜色数组与递归栈,都是 O(n)。
✅ 一亿次以内都算轻松,本题只有一百万次,用最朴素的枚举换取"绝对正确、不易写错",是 n ≤ 1000 时最理性的选择。
// 「枚举所有简单路径」在树上的标准写法 // 树上任意两点之间的简单路径唯一 ⇒ 枚举起点 s,DFS 一次就覆盖了所有终点 t for (int s = 1; s <= n; s++) dfs(s, 0, 1, col[s]); // dep = 1、blk = col[s]:别忘起点 void dfs(int u, int fa, int dep, int blk) { if (blk > k) return; // 约束类剪枝:越走越差,果断停 best = max(best, dep); // 合法状态就统计 for (int v : g[u]) if (v != fa) // 树上"不重复"= 不回头 dfs(v, u, dep + 1, blk + col[v]); } // 复杂度:n 次 DFS × O(n) = O(n²),n ≤ 1000 完全够 // 如果 n 放大到 2e5: // · 最长链类问题 → 树的直径(两次 DFS / BFS) // · 带黑点数上限 → 树形 DP:dp[u][j] = 以 u 为端点的最长链(黑点数 j) // 再用两条子树链拼出"过 u 的折线"更新答案 // 通用经验: // 1) 先看数据范围:n ≤ 1000 ⇒ 放心 O(n²) // 2) 再看约束能不能剪枝:本题 blk 只增不减 ⇒ 超限即停 // 3) "树上不重复结点" 永远翻译成 "v != fa"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 树上路径枚举 | 每个点当起点 DFS,覆盖全部 (s, t) | 树上路径长度 / 计数 / 统计类问题 |
| 搜索中带约束剪枝 | blk > k 立即停 | 约束单调变差的搜索(背包搜索、可行性剪枝) |
| 路径上的多重统计 | dep 与 blk 同步维护 | 路径上求和 / 计数 / 最值 |
| O(n²) 的合理性判断 | n ≤ 1000 时约 10⁶,直接暴力 | 所有"先估范围、再定算法"的题目 |
| 双向加边 | 无向树两个方向都加 | 一切树 / 无向图遍历 |
n 放大到 2 × 10⁵,O(n²) 就不行了,你会怎么做?(提示:把"路径"拆成"以某点为最高点的折线",用树形 DP 维护 dp[u][j] = 从 u 往下的、恰好用 j 个黑点的最长链,再用两条子树的最长链拼起来更新"过 u 的折线"的答案。复杂度 O(n k),k 小时非常高效。先把暴力写对,再想优化——这是竞赛里最稳的递进路线。)