Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1156.

Problem Description

Xiao Yang has a tree with $n$ nodes. Each node in the tree is either white or black.

Xiao Yang wants to know the distance between the farthest pair of nodes that have different colors.

Input Format

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The second line contains $n$ non-negative integers $a_1,a_2,\cdots,a_n$ (for all $1\le i\le n$, $a_i$ equals $0$ or $1$). If $a_i=0$, then node $i$ is white; if $a_i=1$, then node $i$ is black.

Then there are $(n-1)$ lines. Each line contains two positive integers $x_i,y_i$, meaning there is an edge connecting node $x_i$ and node $y_i$.

It is guaranteed that in the input tree, there exist nodes with different colors.

Output Format

Output one integer, representing the distance between the farthest pair of nodes with different colors.

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

3

Hint

Sample Explanation

The farthest pair of nodes with different colors is node $2$ and node $5$.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1\le n\le 10^5$ and $0\le a_i\le 1$.

Translated by ChatGPT 5