ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
6185: [GESP202409 八级] 美丽路径
内存限制:256 MB
时间限制:2 S
题面:传统
评测方式:文本比较
上传者:
提交:2
通过:2
提交
提交记录
统计
Web Board
题目描述
小杨有一棵包含 $n$ 个节点的树,节点从 $1$ 到 $n$ 编号。每个节点要么是白色,要么是黑色。
对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图,其中节点 $1$ 和节点 $4$ 是黑色,其余节点是白色,路径 $2-1-3-4$ 是美丽路径,而路径 $2-1-3-5$ 不是美丽路径(相邻节点 和 颜色相同)。
对于树上一条简单路径,小杨认为它的长度是路径包含的节点数量。小杨想知道最长美丽路径的长度是多少。
输入格式
第一行包含一个正整数 $n$,表示节点数量。
第二行包含 $n$ 个整数 $c_1, c_2, c_3, \dots c_n$,代表每个节点的颜色。如果 $c_i = 0$,节点 $i$ 为白色;如果 $c_i = 1$,节点 $i$ 为黑色。
之后 $n - 1$ 行,每行两个正整数 $u_i, v_i$,表示树上一条边。
输出格式
输出一行一个整数表示答案。
输入样例
复制
5 1 0 0 1 0 1 2 3 5 4 3 1 3
输出样例
复制
4
数据范围与提示
| 子任务 | 占比 | $n$ | 特殊约定 |
| :-: | :-: | :-: | :-: |
| $1$ | $30\%$ | $\leq 1000$ | 树的形态是一条链 |
| $2$ | $30\%$ | $\leq 1000$ | 无 |
| $3$ | $40\%$ | $\leq 10^5$ | 无 |
对全部的测试数据,保证 $1 \leq n \leq 10^5$,$0 \leq c_i \leq 1$,保证给出的是一棵树。