P10725 [GESP202406 Level 8] Farthest Pair of Points

Related multiple-choice and true/false questions: .

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.

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 one integer, representing the distance between the farthest pair of nodes with different colors.

#### Sample Explanation The farthest pair of nodes with different colors is node $2$ and node $5$. #### Constraints **This problem uses bundled testdata.** | Subtask ID | Score | $n$ | $a_i$ | Special Condition | | :--: | :--: | :--: | :--: | :--: | | $1$ | $30$ | $\le 10^5$ | $0\le a_i\le 1$ | The tree is a chain | | $2$ | $30$ | $\le 10^3$ | $0\le a_i\le 1$ | | | $3$ | $40$ | $\le 10^5$ | $0\le a_i\le 1$ | | For all testdata, it is guaranteed that $1\le n\le 10^5$ and $0\le a_i\le 1$. Translated by ChatGPT 5