GESP 2024年9月 美丽路径 题解｜动态规划详细讲解

这是 GESP 2024年9月 的一道动态规划题。题目本身不难，但有几个地方特别容易出错，我把踩过的坑都写出来，希望能帮刚学到这里的朋友少走弯路。

题目来源：ACGO A75469 ｜ 2024年9月 八级赛事场次：2024年9月 八级

一、题目信息

题目名称：美丽路径

赛事场次：2024年9月 八级

难度定位：八级

涉及知识点：动态规划

题目链接：https://www.acgo.cn/problemset/info/75469

坑点（无数人 WA 的核心）

• 状态定义、状态转移方程、初始化、遍历顺序四要素。

题意简述

小杨有一棵包含 n 个节点的树，节点从 1 到 n 编号。每个节点要么是白色，要么是黑色。

对于树上的一条简单路径（不经过重复节点的路径），小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图，其中节点 1 和节点 4 是黑色，其余节点是白色，路径 2-1-3-4 是美丽路径，而路径 2-1-3-5 不是美丽路径（相邻节点 和 颜色相同）。


对于树上一条简单路径，小杨认为它的长度是路径包含的节点数量。小杨想知道最长美丽路径的长度是多少。

前置知识

这道题用到的前置知识不多，我们先把它补齐，即使你刚学到这里也能看懂。

整数除法与取余：C++ 中两个整数相除结果仍是整数，小数部分直接舍去，例如 5/2 得到 2 而不是 2.5。要得到小数必须先把其中一个数转成 double。取余运算：a % b 得到 a 除以 b 的余数，常用来判断整除关系，例如 n % 2 == 0 表示 n 是偶数。

二、思路分析

先看清楚题目要我们做什么

把题目读两遍，我们提取出关键信息：输入是什么、要输出什么、有哪些约束条件。这道题考查的是动态规划，属于这类题里比较基础的一道，把题目要求一步步翻译成代码逻辑就能解决。

我的思考过程

读完题之后，我的第一反应是这样的：对于颜色相同的两条边，我们可以直接忽视，这样这棵树就变成了 1 个及以上的连通块，显然这些连通块也是树。对于每一棵树，它的最长路径就是这颗树的直径。因此求出每棵树的直径取最大值即为答案。

需要说明的是，上面这个思路是把题目要求直译成代码得到的，没有用到什么高级技巧。对于这类基础题，读准题意加写对边界比追求巧妙解法更重要，因为考试里这种题是必须拿满分的。

三、完整代码 + 逐行注释

// 美丽路径：删除同色边后每个连通块求直径，取最大。O(n) 树形 DP
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[100005];
int col[100005];
int ans = 0; // 初始化
int dfs(int u, int fa) { // 返回以 u 为端点的向下最长美丽链长度（节点数）
int best1 = 0, best2 = 0;
for (int v : g[u]) if (v != fa) { // 遍历
int d = dfs(v, u);
if (d > best1) { best2 = best1; best1 = d; } // 判断
else if (d > best2) best2 = d; // 判断
}
ans = max(ans, best1 + best2 + 1);
return best1 + 1;
}
int main() {
int n; scanf("%d", &n);
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);
if (col[u] != col[v]) { g[u].push_back(v); g[v].push_back(u); } // 判断
}
dfs(1, 0);
printf("%d\\n", ans);
return 0;
}

四、代码分段拆解

为了看得更清楚，我们把代码按功能分成几段解释。

第一步：引入头文件

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#include <iostream> 提供输入输出功能，using namespace std; 让我们能直接写 cin、cout 而不用加前缀。这两行是几乎所有 C++ 程序的开头，照写即可。

第二步：读入数据

int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
int u, v; scanf("%d%d", &u, &v);

注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用 long long。

第三步：核心处理逻辑

for (int v : g[u]) if (v != fa) {
for (int i = 1; i < n; i++) {

这一段是整道题的关键，也是动态规划的体现。看循环的三个要素：从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错，结果都会不对。

第四步：按要求输出

printf("%d\\n", ans);

输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA，这种分丢得最可惜。

五、实例模拟

光看代码可能还不够直观，我们用题目的样例实际跑一遍，看看程序是怎么走的。

以题目的第一组样例为例：

样例输入

5
1 0 0 1 0
1 2
3 5
4 3
1 3

样例输出

4

把这份输入代进代码，程序会先把数据依次读入，然后进入循环逐个判断，把满足条件的值累积起来，最后按格式输出。建议你对照着代码在纸上走一遍前两次循环，确认自己对每一步的理解都和程序一致。

题目另外还给了 1 组样例，做完之后建议把剩下的样例都跑一遍，全部通过再提交，能避开大部分边界问题。

六、踩坑总结

下面是做这道题时最容易出错的地方，对照自己的代码检查一下：

七、知识点拓展

最后总结一下这道题带给我们的通用经验：

• 本题考查动态规划的基本写法，这类题在考试中属于必得分项，要练到能默写。
• 写完代码后建议自己造几组边界数据测试，特别是最小值和最大值。
• 同一知识点在不同场次反复出现，把这道题的写法吃透，后面遇到同类题可以直接套用。

八、适用人群

如果你已经掌握动态规划的基本写法，这道题可以用来巩固手感。

如果这篇题解对你有帮助，欢迎点赞收藏。后续我会继续按场次整理 2024年9月 八级 的真题，关注我可以第一时间看到更新。有更好的写法也欢迎在评论区交流。