#G1058. [GESP202406 八级] 最远点对

[GESP202406 八级] 最远点对

[GESP202406 八级] 最远点对

题目描述

小杨有一棵包含 nn 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。

小杨想知道相距最远的一对不同颜色节点的距离是多少。

输入格式

第一行包含一个正整数 nn,代表树的节点数。

第二行包含 nn 个非负整数 a1,a2,…,ana_1, a_2, \dots, a_n(对于所有的 1≤i≤n1 ≤ i ≤ n,均有 aia_i 等于 00 或 11),其中如果 ai=0a_i = 0,则节点 ii 的颜色为白色;如果 ai=1a_i = 1,则节点 ii 的颜色为黑色。

之后 n−1n-1 行,每行包含两个正整数 xi,yix_i, y_i,代表存在一条连接节点 xix_i 和 yiy_i 的边。

保证输入的树中存在不同颜色的点。

输出格式

输出一个整数,代表相距最远的一对不同颜色节点的距离。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例解释

相距最远的不同颜色的一对节点为节点 22 和 55。

数据范围

子任务编号 数据点占比 nn aia_i 特殊条件
1 30% ≤105≤ 10^5 0≤ai≤10 ≤ a_i ≤ 1 树的形态为一条链
2 ≤103≤ 10^3 无
3 40% ≤105≤ 10^5
  • 对于全部数据,保证有 1≤n≤1051 ≤ n ≤ 10^5,0≤ai≤10 ≤ a_i ≤ 1。

时间限制:1.0 s。内存限制:512.0 MB。