GESP 题解库 / 8 级题解 / [GESP202409 八级] 美丽路径 · 第 13 / 24 题
GESP202409 八级 · P11251 · 中等

美丽路径

树形 DP:枚举"路径的最高点",把两条颜色交替的向下链拼起来。

🌳
n ≤ 10⁵
节点数量
⚫
cᵢ ∈ {0, 1}
黑 / 白两色
⚡
O(n)
一次后序遍历
🎯
两条异色链拼接
核心套路
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

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

对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的,当且仅当路径上相邻节点的颜色均不相同。例如节点 1 和节点 4 是黑色、其余节点是白色时,路径 2 − 1 − 3 − 4 是美丽路径,而路径 2 − 1 − 3 − 5 不是美丽路径(相邻节点 3 和 5 颜色相同)。

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

输入格式

第一行一个正整数 n,代表节点数量。

第二行 n 个整数 c₁, c₂, …, cₙ,代表每个节点的颜色:cᵢ = 0 为白色,cᵢ = 1 为黑色。

之后 n − 1 行,每行两个正整数 uᵢ, vᵢ,代表存在一条连接节点 uᵢ 和节点 vᵢ 的边。

输出格式

输出一个整数,代表最长美丽路径的长度(节点数)。

样例

样例输入输出
#15
1 0 0 1 0
1 2
3 5
4 3
1 3
4
#25
0 0 0 0 0
1 2
2 3
3 4
4 5
1
💡
人话翻译:在树上找一条最长的"颜色黑白交替"的简单路径,答案报的是它包含的节点个数(不是边数!)。
一个节点的路径天然满足"相邻都不同"(没有相邻),所以答案至少是 1——这也是样例 2 的答案:一条全白的链,任何相邻两点都同色,能选的只有单个节点。
怎么想?树上任意一条路径,总可以找到一个离根最近的节点 u,于是这条路径 = "从 u 往下的一条链" + 反方向"从 u 往下的另一条链"(两条链可能有一条是空的)。
两条链各自都必须是颜色交替的,而且第一步都必须与 u 异色。
于是只要对每个 u 求出它往下最长的两条异色子链,拼起来就是"以 u 为最高点"的最长美丽路径,全体取最大即可。

🔍 关键词提取

树形 DP最长简单路径颜色交替两链拼接迭代 BFS 防爆栈

已知条件

项目说明
输入第一行 n;第二行 n 个颜色;随后 n − 1 行每行一条边的两个端点
输出最长美丽路径包含的节点数
数据范围1 ≤ n ≤ 10⁵,0 ≤ cᵢ ≤ 1
树形保证输入一定构成一棵树(连通且无环)
边数恰好 n − 1 条;n = 1 时一行边都没有
部分分30% 是一条链;30% 是 n ≤ 1000;40% 是 n ≤ 10⁵

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 以每个点为最高点,拼两条异色向下链
🧠 状态定义
dp[u] = 从 u 出发向下的最长异色链(含 u)
只允许接"与 u 颜色不同"的子结点
叶子结点 dp = 1
单结点路径天然合法
🔁 转移
在两个最大的 dp[子] 里取 top1、top2(异色子结点)
dp[u] = 1 + top1
没有合格子结点时 dp[u] = 1
只扫子结点,跳过父结点
✂️ 答案合并
ans = max(ans, 1 + top1 + top2)
两链分处不同子树 → 拼起来仍是简单路径
只有一条合格链时就退化成 1 + top1
答案至少为 1
⚠️ 易错点
答案报节点数而不是边数
忘记"颜色必须不同"这层过滤
递归 DFS 爆栈
把父结点当子结点重复计算
03
样例手算推导
样例 1 逐条路径核对 + 样例 2 的"退化"解释

🧮 样例 1 手推:路径 2 − 1 − 3 − 4 长度为 4

先把样例 1 的树画清楚。四条边是 1−2、3−5、4−3、1−3,所以 1 连着 2 和 3,3 连着 4 和 5;颜色是 c₁ = 1(黑)、c₂ = 0(白)、c₃ = 0(白)、c₄ = 1(黑)、c₅ = 0(白)。

把所有候选路径摆出来,一条条验证"相邻是否都不同色":

路径颜色序列相邻是否都不同长度(节点数)
2 − 1 − 3 − 4白、黑、白、黑✅ 全部不同4
2 − 1 − 3 − 5白、黑、白、白❌ 3 与 5 同色不合法
4 − 3 − 5黑、白、白❌ 3 与 5 同色不合法
2 − 1 − 3白、黑、白✅3
4 − 3 − 1黑、白、黑✅3
5 − 3 − 1 − 2白、白、黑、白❌ 5 与 3 同色不合法
任意单点 / 异色相邻对—✅1 或 2

最长 = 4(走 2 → 1 → 3 → 4)✓

用树形 DP 跑一遍(以 1 为根)

1
先定根、再按逆序处理

迭代 BFS 从 1 出发:父结点关系为 1 → 2、1 → 3、3 → 4、3 → 5

逆序处理顺序:4、5、3、2、1(先叶子后根)

访问序与父结点都拿到了

2
叶子结点:dp[4] = dp[5] = dp[2] = 1

叶子没有子结点,两条链都是空的

dp[4] = 1,dp[5] = 1,dp[2] = 1

以它们为最高点的路径长度=1

✅ 三个叶子都记 1

3
结点 3:两个子结点 4、5,只有 4 异色

4 的颜色 1,3 的颜色 0 → 异色,dp[4] = 1

5 的颜色 0,3 的颜色 0 → 同色,不能接

top1 = 1、top2 = 0 → dp[3] = 1 + 1 = 2

ans = max(1, 1 + 1 + 0) = 2

✅ dp[3] = 2

4
结点 1:两个子结点 2、3,都异色

2 的颜色 0 ≠ 1 → dp[2] = 1

3 的颜色 0 ≠ 1 → dp[3] = 2

top1 = 2(来自结点 3)、top2 = 1(来自结点 2)

dp[1] = 1 + 2 = 3

ans = max(2, 1 + 2 + 1) = 4

✅ 答案 4

🔑
看清拼接的那一步:1 + top1 + top2 = 1 + 2 + 1 = 4 对应的正是路径 4 − 3 − 1 − 2:一条链 1 → 3 → 4(长度 2,来自 dp[3]),另一条链 1 → 2(长度 1)。
两条链分处 3 号子树和 2 号子树,拼起来没有重复节点,所以必然是一条合法简单路径。
颜色上:白(2) 黑(1) 白(3) 黑(4),每一步都异色——因为两条链的"第一步异色"加上各自内部的交替性,已经覆盖了整条路径的每一对相邻点。

🧮 样例 2:全白的链为什么答案是 1?

样例 2 是 5 个全白节点串成一条链:1 − 2 − 3 − 4 − 5。

链上的路径就是一段连续区间。只要这段区间长度 ≥ 2,它一定包含一对相邻的同色节点,于是不美丽。所以能选的只有单个节点,答案是 1。

候选路径颜色序列是否美丽
1白✅
1 − 2白、白❌
1 − 2 − 3白、白、白❌
2 − 3 − 4 − 5白、白、白、白❌
1 − 2 − 3 − 4 − 5全白❌
1
dp 会全部变成 1

叶子 5:dp = 1

结点 4:唯一子结点 5 同色 → top1 = top2 = 0 → dp[4] = 1

同理倒推回去:dp[3] = dp[2] = dp[1] = 1

每个结点都是一条长度 1 的"链"

2
ans 一直是 1

每处理一个结点,候选值都是 1 + 0 + 0 = 1

ans = max(1, 1) = 1 不增长

✅ 答案 1

⚠️
这个样例专门用来暴露两个常见错误:① 把答案当成"边数"——如果输出 0 就说明你算的是边数(本题要节点数,单点路径长度为 1);② 忘记颜色过滤——如果不过滤颜色,一条全白链会被算成长度 5,直接挂掉。
04
解法对比
树形 DP(正解)vs 带颜色判定的两次 BFS / 暴力枚举路径

⚔️ 解法对比

🟢 树形 DP:最高点 + 两条异色子链(推荐) 推荐

先迭代 BFS 定根,再按逆序算 dp[u](向下最长异色链),用 top1 + top2 更新答案

  • 时间 O(n),空间 O(n)
  • n = 10⁵ 时不到 1 毫秒
  • 代码约 40 行
  • 换根 / 多约束也容易扩展
💡
正确性来源:任意简单路径都有一个"最靠近根的最高点 u",去掉 u 之后剩下的部分必然落在两个不同的子树里,各自是一条向下的链。所以枚举 u 就枚举到了所有路径,一个不漏。

🟠 两次 BFS 求"直径"

从任意点 BFS 找最远点 A,再从 A 找最远点 B,认为 AB 就是答案

  • 时间 O(n),看起来更短
  • 但前提不成立
  • 它求的是"最长路径",不是"最长异色路径"
  • 颜色约束无法用两次 BFS 表达
⚠️
为什么两次 BFS 会挂:两次 BFS 求直径依赖"树上最长路满足三角不等式可拼接"这一性质,而本题最长路是带颜色交替约束的,两个"局部最长"接起来可能因为颜色撞车而报废,贪心地走最远点得不到全局最优。

📈 性能对比

方案复杂度结论
树形 DP(两链拼接)O(n)✅ 正确,本题正解
两次 BFS 求直径O(n)❌ 无视颜色约束,会被反例卡掉
枚举所有 (u, v) 并判路径O(n²) 甚至 O(n³)❌ n = 10⁵ 必超时
递归 DFS 版树形 DPO(n)⚠️ 复杂度对,但 n = 10⁵ 的链会爆栈
05
算法流程图
一次迭代 BFS 定根 + 一次逆序后序遍历
开始读入 n、颜色 c₁…cₙ 与 n − 1 条边用显式栈从 1 出发迭代 BFS,得到访问序 order 与父结点 par按 order 的逆序取出结点 u(自底向上)top1 = top2 = 0(两条最长的异色向下链)枚举 u 的每个子结点 vcolor[v] ≠ color[u] 吗?是 ✓更新 top1 / top2否 ✗跳过这条链dp[u] = 1 + top1ans = max(ans, 1 + top1 + top2)order 还没走完吗?输出 ans继续处理上一个结点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 最长美丽路径计算器(树形 DP)

第一行输入 n,第二行输入 n 个颜色(0 白 / 1 黑),随后 n − 1 行每行一条边的两个端点。程序会用迭代 BFS 定根并做一次后序 DP,展示每个结点的 dp 值与最优路径。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码(迭代树形 DP)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int n;
int col[MAXN];
vector<int> g[MAXN];
int par[MAXN];          // 父结点(以 1 为根)
int order[MAXN], cnt;   // 迭代 BFS 的访问序
int dp[MAXN];           // dp[u]:从 u 出发向下的最长"异色链"(含 u)

int main() {
    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);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 1) 迭代 DFS 定根,得到访问序 order 与父结点 par(不用递归,避免爆栈)
    par[1] = 0;
    vector<int> stk;
    stk.push_back(1);
    while (!stk.empty()) {
        int u = stk.back(); stk.pop_back();
        order[cnt++] = u;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == par[u]) continue;      // 不回头走父结点
            par[v] = u;
            stk.push_back(v);
        }
    }

    // 2) 按访问序的逆序做树形 DP(自底向上)
    int ans = 1;
    for (int idx = cnt - 1; idx >= 0; idx--) {
        int u = order[idx];
        int top1 = 0, top2 = 0;             // 两条最长的异色向下链
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == par[u]) continue;      // 只看子结点
            if (col[v] == col[u]) continue; // 颜色相同,不能接
            if (dp[v] > top1) { top2 = top1; top1 = dp[v]; }
            else if (dp[v] > top2) { top2 = dp[v]; }
        }
        dp[u] = 1 + top1;                                  // u 作为端点向下延伸
        ans = max(ans, 1 + top1 + top2);                   // u 作为最高点拼接两条链
    }

    printf("%d\n", ans);
    return 0;
}
🔑
三个要点:① 不要写递归——n = 10⁵ 的链会让递归深度到 10⁵,必须用显式栈迭代;② 逆序做 DP——只有先算完子结点,父结点才能拿到 dp[子];③ 答案是节点数,所以初值 ans = 1、dp[u] = 1 + top1 里的那个 1 就是 u 自己。

📖 关键几行怎么看

代码作用为什么这样写
if (v == par[u]) continue;跳过父结点树以 1 为根定向后,父结点不能当子结点算
if (col[v] == col[u]) continue;颜色过滤美丽路径的核心约束,同色子链一律不能接
if (dp[v] > top1) { top2 = top1; top1 = dp[v]; }维护 top1 / top2一次扫描同时得到最长与次长两条链
dp[u] = 1 + top1;单链状态u 作为端点,向"链最长"的那一侧延伸
ans = max(ans, 1 + top1 + top2);拼接更新答案u 作为最高点,两条链分别向左下与右下延伸
⚠️
五个坑:① 答案写成边数(漏掉那个 1);② 忘记 col[v] == col[u] 的过滤,样例 2 会输出 5;③ 递归 DFS 定根——n = 10⁵ 的链爆栈;④ 在 dp[u] 里用 1 + top1 + top2(那是路径长度,不是链长度,会连锁放大错误);⑤ n = 1 时没有边,读入循环要写成 i < n 而不是固定 n − 1 次(其实一样,但要注意数组别越界)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
5
1 0 0 1 0
1 2
3 5
4 3
1 3
4题面样例 1:走 2 − 1 − 3 − 4
5
0 0 0 0 0
1 2
2 3
3 4
4 5
1题面样例 2:全白链,任何两相邻点都同色
1
0
1只有一个结点,没有边,答案 1
4
0 1 0 1
1 2
2 3
3 4
4一条完整交替链,整条都能用上
4
0 1 0 1
1 2
1 3
1 4
3菊花图:中心只挑两条异色链拼接
5
0 1 1 0 1
1 2
2 3
3 4
4 5
3链中间出现同色断点,只能截取最长的一段
6
0 1 0 1 1 0
1 2
2 3
3 4
1 5
5 6
6关键用例:两条长链在结点 1 处拼接(1 + 3 + 2)
3
1 1 1
1 2
2 3
1全黑链,颜色过滤必须生效
✅
自查清单:① 是迭代定根吗?② 逆序处理结点吗?③ 过滤了同色与父结点吗?④ dp[u] = 1 + top1、ans = max(ans, 1 + top1 + top2) 写对了吗?

🚨 易错点清单

⚠️
答案报边数:本题输出节点数,单点路径长度为 1,初值 ans = 1 不能丢。
⚠️
忘记颜色过滤:只按"最长向下链"转移而不检查 color[v] ≠ color[u],样例 2 会输出 5。
⚠️
递归爆栈:n 可达 10⁵,链状数据下递归深度 10⁵,必须迭代定根。
⚠️
把父结点当子结点:DP 时若不过滤 v == par[u],会把父结点方向也当成一条链,答案偏大。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
定根方式
显式栈迭代 BFS
n 上限
10⁵

时间怎么算的?

空间都用在哪?

邻接表存 2(n − 1) 条无向边,即 O(n) 个整数;另外需要 col、par、order、dp 各 O(n) 的数组。

✅ n = 10⁵ 时总操作量约几万次比较,远低于 1 秒时限,真正的风险不是速度而是递归爆栈。

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

🔗 常用技巧小抄

// 「树上"带约束的最长路径"」通用树形 DP 模板
// 1) 迭代定根(必须,防爆栈)
vector<int> stk; stk.push_back(1); par[1] = 0;
while (!stk.empty()) {
    int u = stk.back(); stk.pop_back();
    order[cnt++] = u;
    for (int v : g[u]) {
        if (v == par[u]) continue;
        par[v] = u; stk.push_back(v);
    }
}

// 2) 逆序后序遍历:dp[u] 只与子结点的 dp 有关
for (int idx = cnt - 1; idx >= 0; idx--) {
    int u = order[idx], top1 = 0, top2 = 0;
    for (int v : g[u]) {
        if (v == par[u]) continue;
        if (!ok(u, v)) continue;        // 本题:col[v] != col[u]
        if (dp[v] > top1) { top2 = top1; top1 = dp[v]; }
        else if (dp[v] > top2) top2 = dp[v];
    }
    dp[u] = 1 + top1;                   // u 作为端点
    ans = max(ans, 1 + top1 + top2);    // u 作为最高点,两链拼接
}

// 3) 只要把 ok(u, v) 换成别的约束,就能解决一大类问题:
//    · 相邻权值和 <= 限制       -> 单调栈 / 二分优化
//    · 相邻字符不同              -> 本题
//    · 路径上异色点数 <= k       -> dp 加一维计数
//    · 边权最大 / 最小受限        -> dp 记极值

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
迭代定根用显式栈把无根树定向为以 1 为根的树所有深树问题(n ≥ 10⁵ 的链)
后序 DP按访问序逆序处理,只依赖子结点的 dp子树统计、子树最大值、换根 DP 的预处理
top1 / top2 双最值一次扫描同时取最长与次长,用于"拐点拼接"树的直径、两个方向延伸的最优解
颜色过滤把"状态合法"写成一句 ok(u, v)相邻必须异色 / 同类 / 差值受限的路径计数与最优化
🌟
思考题:如果题目改成"路径上至多经过 k 个黑点"(这正是 GESP 八级 202412 的"树上移动"),这套 DP 还能用吗?(提示:能。把状态升级成 dp[u][j] = 从 u 向下、恰好经过 j 个黑点的最长链,转移时给黑点加 1,最后对每个 u 用两个不同子结点的状态"错位"拼起来——把"单一最大值"升级成"数组 + 卷积式合并",是这类题的通用推广。)