题目背景

2024 年 9 月 GESP C++ 八级编程第 2 题

题目描述

给定一棵 $n$ 个节点的树，每个节点为白色或黑色。一条简单路径是美丽的，当且仅当路径上任意相邻两个节点颜色都不同。路径长度定义为路径包含的节点数量。

请计算树上最长美丽路径的长度。

输入格式

第一行输入正整数 $n$。 第二行输入 $n$ 个整数 $c_1,c_2,ldots,c_n$，$0$ 表示白色，$1$ 表示黑色。 接下来 $n-1$ 行，每行输入两个正整数 $u_i,v_i$ 表示一条边。

输出格式

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

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

4

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

1

数据范围与提示

• $1 \le n\le 10^5$，$c_iin{0,1}$。
• 部分数据满足树为链或 $n \le 1000$。
• 若没有颜色不同的相邻边，单个节点也可视为长度为 $1$ 的美丽路径。

来源

GESP 2024 年 09 月 C++ 八级 T2