美丽路径 题解

题目分析

我们有一棵树，共 $n$ 个节点。每个节点非黑即白（$0$ 表示白，$1$ 表示黑）。我们称一条简单路径是美丽的，当且仅当路径上相邻节点的颜色都不相同。换句话说，就是路径上的颜色是严格交替出现的。

路径的长度定义为路径上节点的个数。题目要求我们求出整棵树中最长美丽路径的长度。

数据规模

• 对于 $n \le 1000$ 的情况，可以用较暴力的做法通过前 60% 的数据；
• 对于 $n \le 10^5$ 的大数据，需要 $O(n)$ 或 $O(n \log n)$ 的解法。

本题要求我们在 $O(n)$ 时间内得到答案。

解题思路

“最长相邻不同色路径”是典型的树上 DP（树形动态规划） 问题，类似于求树的直径，只不过这里的“直径”被赋予了颜色交替的约束。

在没有颜色约束时，树的直径可以通过两次 DFS 或者一次树形 DP 求得。这里由于有颜色的约束，一条边只有当两端节点颜色不同时才是“可行”的，因此我们只需要在颜色不同的相邻节点之间进行转移。

核心思想：树形 DP 求带约束的直径

定义 DFS 函数 dfs(x, fa)，返回的是从节点 $x$ 出发，向子树内部延伸（不经过父节点）所能到达的最大深度差（或者理解为向下走的最长合法路径长度，算上起点）。深度差是相对于整棵树的根而言的，我们维护一个全局数组 dep[x] 表示节点 $x$ 在以某个根为参照时的深度。

在 dfs(x, fa) 中：

1. 首先标记当前节点已访问，并记录 dep[x] = dep[fa] + 1。
2. 然后遍历 $x$ 的所有子节点 $i$：
   • 如果 $i$ 是父节点 $fa$，跳过；
   • 如果 $c[i] == c[x]$（颜色相同），则这条边不能成为美丽路径的一部分，也跳过；
   • 否则，递归调用 dfs(i, x)，得到从 $i$ 出发向下延伸的最长路径长度（用一个相对值表示，比如深度）。
3. 在所有合法的子节点返回的结果中，我们收集这些深度值，然后找出最大的两个。用这两条从 $x$ 向下延伸的路径，可以通过节点 $x$ 拼接成一条更长的路径。这条路径的长度为： [ \text{len} = (\text{最深路径深度} - dep[x] + 1) + (\text{次深路径深度} - dep[x] + 1) - 1 ] 即： [ \text{len} = \text{最深深度} + \text{次深深度} - 2 \times dep[x] + 1 ] 这其实就是两条“向下深度差”之和再加 1（当前节点）。
4. 用该长度更新全局最优答案 ans。
5. 最后，dfs 函数返回从 $x$ 出发向下的最大深度值（最终会被父节点用来拼接）。

这个做法和求普通树的直径的 DP 如出一辙，只是只沿颜色不同的边走。

处理不连通的情况

题目保证是一棵树，所以理论上一个连通块就够了。但代码中加了 vis 数组和循环检查未访问的节点，可以兼容森林的情况。这里保留这一写法。

算法说明

我们使用一次 DFS 完成计算。

状态定义：

• dep[x]：节点 $x$ 的深度（任意定一个根，比如 1，但代码中 dfs 的 fa 为 0 时表示根的父亲不存在，需确保 dep[0] = 0）。
• dfs(x, fa) 返回值：以 $x$ 为起点，向子树中沿着合法路径能走到的最大深度值（实际上这个深度值是从根往下计算的一个绝对深度，不是长度）。

转移过程：

• 对每个 $x$，枚举邻接点 $i$，跳过父节点和颜色相同的点。
• 对每个可走的 $i$，得到它的返回值 d = dfs(i, x)；
• 维护所有 d 的最大值作为本函数的返回值；
• 同时记录所有 d 值，排序后取最大的两个，计算经过 $x$ 的最长路径长度，更新全局答案。

注意点：

• 若没有可走的子节点，则返回自己的深度 dep[x]；
• 当子树只有一条可延伸路径时，经过 $x$ 的最长路径就是该路径加上 $x$ 本身的一个端点链，但答案至少为 1，长度计算公式在只有 0 或 1 个合法子节点时不会错误地拼接两条路径，代码里有 res = 1 的初始化以及只有当 m > 1 时才更新 res，这样就能正确处理。

例子说明

以样例图为例：
节点颜色：1(黑)、2(白)、3(白)、4(黑)、5(白)
树边：1-2, 1-3, 3-4, 3-5

• 从某个根开始，比如 1。
• dfs(2,1)：2 向下没有其它不同色节点，返回深度 dep[2]。
• dfs(3,1)：3 与 1 同色（白），所以从 1 到 3 这条边不走。
• 但实际上 1 和 2 不同色，所以 1 可以得到 2 的深度。同时 1 与 3 同色不能走。最终 1 的子树返回最长向下深度。
• 在 3 内部，3-4 不同色，3-5 同色，所以 4 返回深度；3 得到 4 的深度，再加上 3 自身，可以拼出路径 3-4。再通过全局更新，最后找到路径 2-1-3-4 长度为 4。

参考代码解释

以下给出完整注释版代码。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1e5 + 10;
5
6vector<int> g[N];    // 邻接表存树
7int dep[N], vis[N], c[N];
8int n, ans;
9
10// 返回值：从 x 出发向下可走到的最大深度
11int dfs(int x, int fa) {
12    vis[x] = 1;
13    dep[x] = dep[fa] + 1;   // 计算深度，dep[0]默认为0
14
15    int mx = dep[x];        // 当前能到达的最大深度初始化为自己
16    vector<int> tmp;        // 收集所有子节点返回的深度值
17    tmp.push_back(mx);      // 把自身深度也放进去，便于统一处理
18
19    for (auto i : g[x]) {
20        // 跳过父节点 或 颜色相同的不合法边
21        if (i == fa || c[i] == c[x]) continue;
22
23        int d = dfs(i, x);   // 获取子树的最大深度
24        tmp.push_back(d);
25        mx = max(d, mx);     // 更新从x向下能走到的最深深度
26    }
27
28    // 从收集的深度值中拿出最大的两个，用于拼接经过x的路径
29    sort(tmp.begin(), tmp.end());
30    int m = tmp.size();
31    int res = 1;            // 至少包含x自己
32
33    if (m > 1) {
34        // 两条最深的路径深度差之和 + 1 (x本身)
35        res = tmp[m - 1] + tmp[m - 2] - 2 * dep[x] + 1;
36    }
37
38    ans = max(ans, res);    // 更新全局最优答案
39    return mx;              // 返回最深深度，供父节点使用
40}
41
42int main() {
43    ios::sync_with_stdio(false);
44    cin.tie(nullptr);
45
46    cin >> n;
47    for (int i = 1; i <= n; ++i) cin >> c[i];
48    for (int i = 1; i < n; ++i) {
49        int u, v;
50        cin >> u >> v;
51        g[u].push_back(v);
52        g[v].push_back(u);
53    }
54
55    // 虽然题目给定是树，但保险起见遍历所有节点
56    for (int i = 1; i <= n; ++i) {
57        if (!vis[i]) {
58            dfs(i, 0);
59        }
60    }
61
62    cout << ans << "\n";
63    return 0;
64}

时间复杂度分析

• 每个节点只会被访问一次（通过 vis 数组保证），每条边最多被考虑两次（无向边在两端各枚举一次）。
• 在 DFS 内部，对每个节点收集子节点的深度值并排序，但每个节点的度数总和为 $2(n-1)$，即在树上所有节点的 tmp 数组长度之和是 $O(n)$ 级别。即便每个节点内部排序，最坏情况下当树是菊花图时，根节点的度数为 $n-1$，排序复杂度 $O(n \log n)$，但这仅仅是极少数节点的情况吗？实际上对于菊花图，根节点会收集 $n-1$ 个值，排序为 $O(n \log n)$，这导致总复杂度可能达到 $O(n \log n)$，在 $n\le 10^5$ 时仍然可以非常快通过。
• 空间复杂度：邻接表等 $O(n)$。

因此，该算法可以在限定的时间和空间内完美解决本题。

---

这道题本质上就是带颜色约束的“树上直径”问题，通过树形 DP 一次 DFS 求得。理解普通树的直径 DP 后，加上颜色判断即可轻松解决。