题目背景

2024 年 6 月 GESP C++ 八级编程第 1 题

题目描述

小杨有一棵包含 $n$ 个节点的树，每个节点为白色或黑色。请找出一对颜色不同的节点，使它们在树上的距离最大，并输出这个最大距离。树上两点距离为连接它们的简单路径上的边数。

输入格式

第一行输入正整数 $n$。 第二行输入 $n$ 个整数 $a_1,a_2,ldots,a_n$，$0$ 表示白色，$1$ 表示黑色。 接下来 $n-1$ 行，每行输入两个正整数 $x_i,y_i$ 表示一条边。 输入保证至少存在一对白色、黑色节点。

输出格式

输出一行一个整数，表示不同颜色节点对的最大距离。

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

3

数据范围与提示

• $1 \le n\le 10^5$，$0 \le a_i \le 1$。
• 部分数据为链形树或 $n \le 10^3$。
• 样例中节点 $2$ 与节点 $5$ 距离为 $3$。

来源

GESP 2024 年 06 月 C++ 八级 T1