树上移动 题解

题目分析

问题可以转化为：在一棵树上找一条简单路径（不经过重复节点），使得路径上的黑色节点数量不超过 $k$，并且路径经过的节点总数尽可能多，求出这个最大值。

移动起点 $s$ 和终点 $t$ 可以任意选择，路径就是树上两点之间的唯一简单路径。因此我们只需要检查树上所有可能路径，找出在黑色节点限制下的最长路径。

解题思路

由于 $n \le 1000$，$O(n^2)$ 的算法完全可以接受。一个朴素而直接的思路是：

• 枚举每一个节点作为路径的起点。
• 从该起点出发，沿树边深度优先搜索（DFS），尝试向各个方向延伸路径。
• 在 DFS 过程中，维护两个计数：
  • cnt1：当前路径已经经过的节点总数。
  • cnt2：当前路径已经经过的黑色节点总数。
• 如果 cnt2 > k，则说明继续走下去会超出黑色节点限制，立即回溯。
• 否则，用 cnt1 更新全局最大值。

这样等价于以每个节点为根进行一次 DFS，搜索所有以该节点为起点的简单路径，并检查约束条件。由于树中任何一条简单路径都可以从它的某个端点开始 DFS 得到，因此算法能够覆盖所有可能的路径。

算法说明

1. 读入数据并建图

   • 使用邻接表 g 存储树的边。
   • 用数组 col 记录每个节点的颜色，0 为白色，1 为黑色。

2. 枚举起点并搜索

   • 对于 $i = 1$ 到 $n$，以节点 $i$ 作为路径起点。
   • 根据起点颜色初始化：
     • 如果 col[i] == 1，则 DFS 初始参数为 cnt1 = 1, cnt2 = 1。
     • 否则为 cnt1 = 1, cnt2 = 0。

3. DFS 函数设计

   • 参数：u 为当前节点，fa 为父节点（避免走回头路），cnt1、cnt2 如上所述。
   • 终止条件：若 cnt2 > k，直接返回，不再向下搜索。
   • 更新答案：在满足条件时，用 cnt1 更新全局最大值 maxn。
   • 遍历邻居：对于 u 的每个子节点 v（v != fa），根据 col[v] 调用新的 DFS：
     • 若 v 为黑色：dfs(v, u, cnt1 + 1, cnt2 + 1)
     • 若 v 为白色：dfs(v, u, cnt1 + 1, cnt2)

4. 输出结果

   • 所有起点枚举结束后，输出 maxn。

时间复杂度分析

• 对 $n$ 个起点分别进行一次 DFS，每次 DFS 最坏会访问树中所有节点。
• 每次 DFS 的时间复杂度为 $O(n)$。
• 总时间复杂度为 $O(n^2)$。

由于本题 $n \le 1000$，$n^2 = 10^6$，在 1 秒的时间限制内完全可以通过。

参考代码

cpp
复制
1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int N = 1e3 + 5;
6
7int n, k, maxn, col[N];
8vector<int> g[N];
9
10// u: 当前节点, fa: 父节点, cnt1: 已经过节点数, cnt2: 已经过黑色节点数
11void dfs(int u, int fa, int cnt1, int cnt2) {
12    if (cnt2 > k) return;           // 黑色节点超限，剪枝返回
13    maxn = max(maxn, cnt1);         // 更新最大节点数
14    for (int i = 0; i < g[u].size(); i++) {
15        int v = g[u][i];
16        if (v != fa) {              // 避免走回父节点
17            if (col[v] == 1)
18                dfs(v, u, cnt1 + 1, cnt2 + 1);
19            else
20                dfs(v, u, cnt1 + 1, cnt2);
21        }
22    }
23}
24
25int main() {
26    cin >> n >> k;
27    for (int i = 1; i <= n; i++) cin >> col[i];
28    for (int i = 1; i < n; i++) {
29        int u, v;
30        cin >> u >> v;
31        g[u].push_back(v);
32        g[v].push_back(u);
33    }
34
35    for (int i = 1; i <= n; i++) {  // 枚举路径起点
36        if (col[i] == 1)
37            dfs(i, 0, 1, 1);
38        else
39            dfs(i, 0, 1, 0);
40    }
41
42    cout << maxn << endl;
43    return 0;
44}

代码解释

• g 是邻接表，vector<int> 数组，用于存储图的结构。
• col 数组存储每个节点的颜色。
• maxn 用于记录全局最大值。
• dfs 函数中，首先判断黑色节点数是否超过 $k$，若超过则不再深入；否则用当前的总节点数更新答案。接着枚举子节点，除父节点外都能走，根据子节点颜色增加对应计数并递归。
• main 函数中，先读入数据建图，然后对每个节点作为起点调用 DFS，最后输出结果。

总结

本题的关键在于发现 $n$ 的范围允许平方级别算法，从而可以使用枚举所有起点的暴力 DFS。对于信息学竞赛中 $n \le 1000$ 的树问题，直接暴力搜索所有路径往往是一种简单可靠的解法。如果数据范围更大（如 $n \le 10^5$），则需要考虑树形 DP 或点分治、双指针/滑动窗口等更高效的方法。