题解：洛谷 P11251 [GESP202409 八级] 美丽路径

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P11251 [GESP202409 八级] 美丽路径 – 洛谷

【题目描述】

小杨有一棵包含

n

n

n 个节点的树，节点从

1

1

1 到

n

n

n 编号，并且每个节点要么是白色，要么是黑色。

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

1

1

1 和节点

4

4

4 是黑色，其余节点是白色，路径

2

−

1

−

3

−

4

2-1-3-4

2−1−3−4 是美丽路径，而路径

2

−

1

−

3

−

5

2-1-3-5

2−1−3−5 不是美丽路径（相邻节点

3

3

3 和

5

5

5 颜色相同）。

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

【输入】

第一行包含一个正整数

n

n

n，代表节点数量。

第二行包含

n

n

n 个整数

c

1

,

c

2

,

…

,

c

n

c_1,c_2,\\dots,c_n

c1​,c2​,…,cn​，代表每个节点的颜色，如果

c

i

=

0

c_i=0

ci​=0，代表节点

i

i

i 为白色，如果

c

i

=

1

c_i=1

ci​=1，代表节点

i

i

i 为黑色。

之后

n

−

1

n-1

n−1 行，每行包含两个正整数

u

i

,

v

i

u_i,v_i

ui​,vi​，代表存在一条连接节点

u

i

u_i

ui​ 和节点

v

i

v_i

vi​ 的边。

【输出】

输出一个整数，代表最长美丽路径的长度。

【输入样例】

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

【输出样例】

4

【核心思想】

【算法标签】

#普及 #树形DP

【代码详解】

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

const int N = 100005, M = N * 2;

int n; // 节点数量
int c[N]; // c[i] 表示节点i的颜色
int f1[N]; // f1[i]: 以节点i为起点的最长同色路径长度
int f2[N]; // f2[i]: 以节点i为起点的次长同色路径长度
int ans; // 最终答案（路径上的节点数-1，即最大长度）
int h[N], e[M], ne[M], idx; // 邻接表存储树

// 添加无向边
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

// 深度优先搜索
// u: 当前节点
// fa: 父节点
void dfs(int u, int fa)
{
// 遍历所有邻接节点
for (int i = h[u]; i != –1; i = ne[i])
{
int j = e[i]; // 邻接节点
if (j == fa) // 跳过父节点
{
continue;
}

// 递归处理子树
dfs(j, u);

// 计算从当前节点u到子节点j的路径长度
// 如果u和j颜色不同，路径长度为f1[j]+1，否则为0
int t = (c[u] != c[j] ? f1[j] + 1 : 0);

// 更新f1[u]和f2[u]
if (t > f1[u])
{
f2[u] = f1[u]; // 原来的最大值变为次大值
f1[u] = t; // 更新最大值
}
else if (t > f2[u])
{
f2[u] = t; // 更新次大值
}
}

// 更新答案：考虑经过节点u的最长同色路径
// 注意：这里计算的是路径上的边数，而不是节点数
ans = max(ans, f1[u] + f2[u]);
}

int main()
{
cin >> n;

// 初始化邻接表
memset(h, –1, sizeof(h));
idx = 0;

// 读取每个节点的颜色
for (int i = 1; i <= n; i++)
{
cin >> c[i];
}

// 读取树的边
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}

// 从节点1开始DFS
dfs(1, 0);

// 输出结果：最长同色路径的节点数 = 边数 + 1
cout << ans + 1 << endl;

return 0;
}

【运行结果】

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