GESP 题解库 / 8 级题解 / [GESP202412 八级] 树上移动 · 第 12 / 24 题
GESP202412 八级 · P11379 · 中等

树上移动:黑点数受限的最长路径

n ≤ 1000,以每个结点为起点 DFS 一遍,O(n²) 枚举全部简单路径。

🌳
n ≤ 1000
结点数
⚫
k ≤ 1000
最多经过的黑点数
⚡
O(n²) ≈ 10⁶
枚举全部路径
🎯
每个点起一次 DFS
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n,每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点 s 和节点 t,并从节点 s 出发移动到节点 t,移动过程中小杨不能够经过重复节点。

小杨希望自己在至多经过 k 个黑色节点的前提下,经过的总节点数尽可能多,请你帮小杨选择经过最多的节点数是多少。

输入输出样例

样例内容
输入 #15 1
0 0 1 1 1
1 2
2 3
2 5
1 4
输出 #13
💡
人话翻译:"不能经过重复节点"加上"图上是一棵树",意思就是走一条简单路径——树上任意两点之间只有唯一一条简单路径。
于是题目等价于:选两个点 s 和 t,让 s → t 这条路径上的黑点数 ≤ k,并且路径上的结点总数尽量多。
再看数据范围:n ≤ 1000,所有路径的数量级是 O(n²) = 10⁶,完全在 1 秒的承受范围内。
所以最省心的做法就是枚举:让每个结点都当一次起点 s,从 s 出发 DFS 整棵树,沿途同时记下 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 表示黑
子任务 120%:n ≤ 100,k ≤ 100,树的形态是一条链
子任务 220%:n ≤ 1000,k = 0
子任务 360%:n ≤ 1000,k ≤ 1000

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 每个结点都当一次起点,O(n²) 枚举全部路径
🧠 问题转化
不重复结点 = 简单路径
树上 s → t 的路径唯一
目标:黑点数 ≤ k 时让 dep 最大
路径包含起点与终点
🔁 枚举方式
让每个结点 s 都当起点
从 s 出发 DFS 整棵树
递归携带 dep 与 blk 两个值
向下走时 dep + 1、blk + col[v]
✂️ 剪枝
blk > k 立即 return
再往下走黑点只会更多
合法时用 dep 更新 best
不需要记录具体路径
⚠️ 易错点
忘记把起点的黑点数算进去
blk > k 时还更新了答案
只考虑"一条直链"漏掉拐弯路径
n = 1 时没有边,读入要小心
03
样例手算推导
样例 1 的全部候选路径逐个排查

🧮 样例 1:n = 5、k = 1,树的形状先看清

颜色:1 = 白、2 = 白、3 = 黑、4 = 黑、5 = 黑;边:1—2、2—3、2—5、1—4。

结点12345
颜色白白黑黑黑

这棵树长这样:3 和 5 挂在 2 下面,4 挂在 1 下面,1—2 是主干。因为 k = 1,路径上最多只能出现一个黑点。

把最有可能的几条路径逐一验算

路径经过的结点黑点数结点数是否可行
3 → 2 → 13、2、11(只有 3)3✅ 可行,最优
4 → 1 → 24、1、21(只有 4)3✅ 可行,同样最优
4 → 1 → 2 → 34、1、2、32(4 和 3)4❌ 黑点 2 > k = 1
3 → 2 → 53、2、52(3 和 5)3❌ 黑点 2 > k = 1
5 → 2 → 1 → 45、2、1、42(5 和 4)4❌ 黑点 2 > k = 1
4 → 1 → 2 → 3(换起点试)4、1、2、324❌ 超过 k
只走一个白点,如 1101✅ 可行但不是最优
1
起点 s = 3 的 DFS

起点 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

2
起点 s = 4 的 DFS

起点 4 是黑的:dep = 1、blk = 1

走到 1(白):dep = 2、blk = 1

走到 2(白):dep = 3、blk = 1 ✅ 与当前最优持平

再走到 3 或 5 都是黑:blk 会变成 2,剪枝

起点 4 也得 3

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"这个答案是怎么来的:它是一条跨过分叉点的路径——3 → 2 → 1 或 4 → 1 → 2。
也就是说,路径可以"拐弯":从一个分支上来、穿过某个结点、再下到另一个分支,只要两端黑点数加起来不超过 k 就合法。
这就是为什么不能只盯着"树上最长的直链"去算。

🧮 k 变大以后,"拐弯路径"会更明显

把样例的 k 从 1 改成 2,再算一遍,你会看到弯路的威力:

路径经过的结点黑点数结点数是否可行
3 → 2 → 1 → 43、2、1、42(3 和 4)4✅ 可行,最优
5 → 2 → 1 → 45、2、1、42(5 和 4)4✅ 同样最优
3 → 2 → 53、2、523✅ 可行但不是最优
1
为什么 3 → 2 → 1 → 4 是合法的

路径依次经过 3(黑)、2(白)、1(白)、4(黑)

黑点共 2 个,恰好等于 k = 2,没有超限

结点数 = 4,比任何一条"直链"都长

它在结点 2 与 1 之间"拐了个弯",穿过了主干

✅ k = 2 时答案变成 4

2
为什么"只看最长直链"会算错

树上的最长直链是 3 → 2 → 1 → 4?

其实这条路本身就是一条路径,但如果只沿着"某条一直往下的链"找

就会得到 2 → 1 → 4(3 个点)或 3 → 2 → 1(3 个点)

漏掉"两个分支接起来"的那条

❌ 只算直链会漏解

⚠️
本题最容易想歪的地方:不要把它当成"求树上最长的一条链"。
题目问的是任意一条简单路径上的结点数,路径完全可以从一个叶子出发、经过若干分叉、到另一个叶子结束。
唯一不会错的做法就是"以每个点为起点 DFS 一次",把所有起点出发的所有路径都过一遍。这也正是 n ≤ 1000 这个范围给出的暗示:出题人允许你用 O(n²)。
04
解法对比
每个起点 DFS(O(n²))vs 树形 DP

⚔️ 解法对比

🟢 每个结点当起点各跑一次 DFS(推荐) 推荐

以 s 为根向下走,携带 dep 与 blk,超限就剪枝,合法就更新答案

  • 时间 O(n²) ≈ 10⁶
  • 空间 O(n)
  • 代码约 20 行,几乎不会写错
  • 不用处理"两条链拼接"的组合细节
💡
为什么它是本题最优选择:n ≤ 1000 时 n² = 10⁶,C++ 几毫秒就能跑完,既然暴力够快,就没有理由去写更容易出错的复杂算法。
而且"每个起点 DFS"天然覆盖了拐弯路径,不需要额外讨论路径形状。

🔵 树形 DP(按黑点数分层)

dp[u][j] 表示从 u 向下、黑点数为 j 的最长链长度,再合并两条子树链

  • 时间 O(n · k)(也可视作 O(n²))
  • 空间 O(n · k)
  • 要处理"两条子树链拼成折线"的合并
  • n ≤ 1000 时两者都能过
⚠️
它的意义在于"可扩展":当 n 放大到 2 × 10⁵ 时,O(n²) 就废了,而 O(nk) 的树形 DP 还能撑住(前提是 k 不大)。
但在本题的数据范围下,写 DP 付出的调试成本换不来任何额外分数。

📈 性能对比

方案复杂度结论
每个起点各跑一次 DFSO(n²) ≈ 10⁶✅ 推荐(本题最稳)
树形 DP 分层合并O(n k)✅ 可行,代码更绕
只求"树上最长直链"O(n)❌ 会漏掉拐弯路径,答案偏小
05
算法流程图
每个起点 DFS 一遍,边搜边剪枝
开始读入 n、k 与 n 个结点颜色读入 n − 1 条边,建成无向树best = 0还有起点 s 没试过吗?从 s 出发 DFS,沿路径累计 dep(结点数)与 blk(黑点数)blk > k 吗?否 ✓用 dep 更新 best,继续扩展到邻居是 ✗这条分支作废,立刻不再深入这个起点的所有分支都走完了吗?输出 best结束换下一个起点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 最长可行路径计算器

第一行输入 n k,第二行输入 n 个颜色(0 白 1 黑),随后 n − 1 行输入一条边。程序会以每个结点为起点 DFS,展示每个起点的最优值、全局答案与一条最优路径。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(每个起点各跑一次 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++ 默认栈足够,不用改。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 1
0 0 1 1 1
1 2
2 3
2 5
1 4
3题面样例:3 → 2 → 1 或 4 → 1 → 2,3 个点 1 个黑点
5 2
0 0 1 1 1
1 2
2 3
2 5
1 4
4k 变大后"拐弯路径" 3 → 2 → 1 → 4 成为最优
4 0
0 0 0 0
1 2
2 3
3 4
4k = 0 且全白:整条链 4 个点都能走
3 1000
1 1 1
1 2
2 3
3全黑但 k 足够大:整条链都能走
4 1
0 1 1 1
1 2
1 3
1 4
2白心菊花,k = 1:走两个黑叶子会变 2 个黑点,只能走"白心 + 一个黑叶"
2 0
0 1
1 2
1k = 0:只能选那个白点自己
1 0
0
1n = 1 没有边,单个白点合法
5 1
0 1 0 1 0
1 2
2 3
3 4
4 5
3黑白交替链:3 → 2 → 1 是 3 个点 1 个黑点
✅
自查清单:① 每个点都当起点了吗?② 起点的黑点数算进去了吗?③ blk > k 剪枝了吗?④ 无向边两个方向都加了吗?

🚨 易错点清单

⚠️
忘记算起点的黑点数:路径包含起点与终点,初始必须是 dep = 1、blk = col[s]。
⚠️
只找"树上最长的直链":路径可以拐弯(如样例 k = 2 时的 3 → 2 → 1 → 4),只盯直链会漏解。
⚠️
超限还更新答案:blk > k 的路径一律不合法,必须放在最前面剪掉。
⚠️
把树当有向图读:边是双向的,只加一个方向就搜不下去了。
⚠️
n = 1 时的输入:颜色行之后没有边了,读入循环不能多读一行。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
路径枚举量
≤ n² 条
n = 1000 时
约 10⁶ 次访问

时间怎么算的?

空间都用在哪?

邻接表 vector<int> g[n + 1] 存 2(n − 1) 条弧,加上颜色数组与递归栈,都是 O(n)。

✅ 一亿次以内都算轻松,本题只有一百万次,用最朴素的枚举换取"绝对正确、不易写错",是 n ≤ 1000 时最理性的选择。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「枚举所有简单路径」在树上的标准写法
// 树上任意两点之间的简单路径唯一 ⇒ 枚举起点 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 小时非常高效。先把暴力写对,再想优化——这是竞赛里最稳的递进路线。)