No.2634 Tree Distance 3
ebi_fly
noya2Problem Statement
You are given a tree $T$ with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertices $u_i$ and $v_i$. Also, $A_i$ is written on vertex $i$. Solve the following problem for each $i = 1,2,\dots,N$.
- Among all $j$ ( $1\leq j \leq N$) such that $A_i \leq A_j$, find the maximum value of the distance $d(i, j)$ between the $2$ vertices $i$, $j$ in the tree $T$.
Here, the distance $d(i, j)$ between $2$ vertices $i$, $j$ of a tree is the number of edges contained in the path whose endpoints are $i$ and $j$.
Constraints
- $2 \leq N \leq 2\times 10^5$
- $0 \leq A_i \leq 10^9$
- $1 \leq u_i, v_i \leq N$
- The graph given in the input is a tree.
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
Output
Output the answers for $i = 1,2,\dots,N$, separated by spaces.
Sample
Sample 1
Input
5 4 2 2 3 1 1 2 1 3 3 4 3 5
Output
0 3 2 2 3
For $i = 1$, the only possible value of $j$ is $1$, so the answer is $0$.
For $i = 2$, the possible values of $j$ are $1$, $2$, $3$, $4$, and the answer is $3$, attained when $j = 4$.
For $i = 3$, the possible values of $j$ are $1$, $2$, $3$, $4$, and the answer is $2$, attained when $j = 2$.
For $i = 4$, the possible values of $j$ are $1$, $4$, and the answer is $2$, attained when $j = 1$.
For $i = 5$, the possible values of $j$ are $1$, $2$, $3$, $4$, $5$, and the answer is $3$, attained when $j = 2$.
Sample 2
Input
6 2 9 1 4 6 8 1 2 1 3 1 4 3 5 3 6
Output
2 0 2 3 3 3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。