树形 DP:枚举"路径的最高点",把两条颜色交替的向下链拼起来。
小杨有一棵包含 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ᵢ 的边。
输出一个整数,代表最长美丽路径的长度(节点数)。
| 样例 | 输入 | 输出 |
|---|---|---|
| #1 | 51 0 0 1 01 23 54 31 3 | 4 |
| #2 | 50 0 0 0 01 22 33 44 5 | 1 |
树形 DP最长简单路径颜色交替两链拼接迭代 BFS 防爆栈
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个颜色;随后 n − 1 行每行一条边的两个端点 |
| 输出 | 最长美丽路径包含的节点数 |
| 数据范围 | 1 ≤ n ≤ 10⁵,0 ≤ cᵢ ≤ 1 |
| 树形保证 | 输入一定构成一棵树(连通且无环) |
| 边数 | 恰好 n − 1 条;n = 1 时一行边都没有 |
| 部分分 | 30% 是一条链;30% 是 n ≤ 1000;40% 是 n ≤ 10⁵ |
u;这条路径必然由"u 向下的一条链"和"另一条向下链"组成,不可能出现分叉两次(树中路径无重复节点)。所以枚举 u 并拼接两条链是完备的u 到子结点的第一步必须异色",因为一旦第一步异色,链上后续的交替性是子结点自己的 dp 值已经保证的——这说明 dp 的定义要写成"从 u 出发向下的最长异色链"n 可达 10⁵,若树退化成一条链,递归深度会达到 10⁵ 层,很可能栈溢出(RE)。用显式栈 / 队列做一次迭代 BFS 先定根,再按访问序逆序做 DP,深度与递归无关先把样例 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)✓
迭代 BFS 从 1 出发:父结点关系为 1 → 2、1 → 3、3 → 4、3 → 5
逆序处理顺序:4、5、3、2、1(先叶子后根)
访问序与父结点都拿到了
叶子没有子结点,两条链都是空的
dp[4] = 1,dp[5] = 1,dp[2] = 1
以它们为最高点的路径长度=1
✅ 三个叶子都记 1
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
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)。样例 2 是 5 个全白节点串成一条链:1 − 2 − 3 − 4 − 5。
链上的路径就是一段连续区间。只要这段区间长度 ≥ 2,它一定包含一对相邻的同色节点,于是不美丽。所以能选的只有单个节点,答案是 1。
| 候选路径 | 颜色序列 | 是否美丽 |
|---|---|---|
| 1 | 白 | ✅ |
| 1 − 2 | 白、白 | ❌ |
| 1 − 2 − 3 | 白、白、白 | ❌ |
| 2 − 3 − 4 − 5 | 白、白、白、白 | ❌ |
| 1 − 2 − 3 − 4 − 5 | 全白 | ❌ |
叶子 5:dp = 1
结点 4:唯一子结点 5 同色 → top1 = top2 = 0 → dp[4] = 1
同理倒推回去:dp[3] = dp[2] = dp[1] = 1
每个结点都是一条长度 1 的"链"
每处理一个结点,候选值都是 1 + 0 + 0 = 1
ans = max(1, 1) = 1 不增长
✅ 答案 1
先迭代 BFS 定根,再按逆序算 dp[u](向下最长异色链),用 top1 + top2 更新答案
从任意点 BFS 找最远点 A,再从 A 找最远点 B,认为 AB 就是答案
| 方案 | 复杂度 | 结论 |
|---|---|---|
| 树形 DP(两链拼接) | O(n) | ✅ 正确,本题正解 |
| 两次 BFS 求直径 | O(n) | ❌ 无视颜色约束,会被反例卡掉 |
| 枚举所有 (u, v) 并判路径 | O(n²) 甚至 O(n³) | ❌ n = 10⁵ 必超时 |
| 递归 DFS 版树形 DP | O(n) | ⚠️ 复杂度对,但 n = 10⁵ 的链会爆栈 |
第一行输入 n,第二行输入 n 个颜色(0 白 / 1 黑),随后 n − 1 行每行一条边的两个端点。程序会用迭代 BFS 定根并做一次后序 DP,展示每个结点的 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; }
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 作为最高点,两条链分别向左下与右下延伸 |
col[v] == col[u] 的过滤,样例 2 会输出 5;③ 递归 DFS 定根——n = 10⁵ 的链爆栈;④ 在 dp[u] 里用 1 + top1 + top2(那是路径长度,不是链长度,会连锁放大错误);⑤ n = 1 时没有边,读入循环要写成 i < n 而不是固定 n − 1 次(其实一样,但要注意数组别越界)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 4 | 题面样例 1:走 2 − 1 − 3 − 4 |
5 | 1 | 题面样例 2:全白链,任何两相邻点都同色 |
1 | 1 | 只有一个结点,没有边,答案 1 |
4 | 4 | 一条完整交替链,整条都能用上 |
4 | 3 | 菊花图:中心只挑两条异色链拼接 |
5 | 3 | 链中间出现同色断点,只能截取最长的一段 |
6 | 6 | 关键用例:两条长链在结点 1 处拼接(1 + 3 + 2) |
3 | 1 | 全黑链,颜色过滤必须生效 |
dp[u] = 1 + top1、ans = max(ans, 1 + top1 + top2) 写对了吗?ans = 1 不能丢。color[v] ≠ color[u],样例 2 会输出 5。v == par[u],会把父结点方向也当成一条链,答案偏大。邻接表存 2(n − 1) 条无向边,即 O(n) 个整数;另外需要 col、par、order、dp 各 O(n) 的数组。
✅ n = 10⁵ 时总操作量约几万次比较,远低于 1 秒时限,真正的风险不是速度而是递归爆栈。
// 「树上"带约束的最长路径"」通用树形 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) | 相邻必须异色 / 同类 / 差值受限的路径计数与最优化 |
dp[u][j] = 从 u 向下、恰好经过 j 个黑点的最长链,转移时给黑点加 1,最后对每个 u 用两个不同子结点的状态"错位"拼起来——把"单一最大值"升级成"数组 + 卷积式合并",是这类题的通用推广。)