27539번 - Cat Exercise 서브태스크다국어

There are $N$ cat towers, numbered from $1$ to $N$. The height of Tower $i$ ($1 ≤ i ≤ N$) is $P_i$. The heights of the towers are distinct integers between $1$ and $N$, inclusive. There are $N - 1$ adjacent pairs of towers. For each $j$ ($1 ≤ j ≤ N - 1$), Tower $A_j$ and Tower $B_j$ are adjacent to each other. In the beginning, it is possible to travel from a tower to any other tower by repeating moves from towers to adjacent towers.

In the beginning, a cat stays in a tower of height $N$.

Then we perform cat exercises. In cat exercises, we repeatedly choose a tower and put an obstacle on it. However, we cannot put an obstacle on a tower where we already put an obstacle on it. During the process, the following will happen.

• If the cat does not stay in the chosen tower, nothing will happen.
• If the cat stays in the chosen tower and there is an obstacle on every tower which is adjacent to the chosen tower, the cat exercises will finish.
• Otherwise, among the towers where the cat can arrive by repeating moves from towers to adjacent towers without obstacles, the cat will move to the highest tower except for the current tower by repeating moves from towers to adjacent towers. In this process, the cat takes the route where the number of moves from towers to adjacent towers becomes minimum.

Given information of the heights of the towers and pairs of adjacent towers, write a program which calculates the maximum possible sum of the number of moves of the cat from towers to adjacent towers if we put obstacles suitably

Read the following data from the standard input.

$N$

$P_1$ $P_2$ $\cdots$ $P_N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{N-1}$ $B_{N-1}$

Write one line to the standard output. The output should contain the maximum possible sum of the number of moves of the cat from towers to adjacent towers.

• $2 ≤ N ≤ 200\,000$.
• $1 ≤ P_i ≤ N$ ($1 ≤ i ≤ N$).
• $P_i \ne P_j$ ($1 ≤ i < j ≤ N$).
• $1 ≤ A_j < B_j ≤ N$ ($1 ≤ j ≤ N - 1$).
• In the beginning, it is possible to travel from a tower to any other tower by repeating moves from towers to adjacent towers.
• Given values are all integers.