| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 225 | 113 | 96 | 48.731% |
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.
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.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $A_i = i,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$), $N ≤ 16$. |
| 2 | 7 | $A_i = i,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$), $N ≤ 300$. |
| 3 | 7 | $A_i = i,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$), $N ≤ 5,000円$. |
| 4 | 10 | $N ≤ 5,000円$. |
| 5 | 20 | $A_i = i,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$). |
| 6 | 23 | $A_i = \left\lfloor\frac{i+1}{2}\right\rfloor,ドル $B_i = i + 1$ (1ドル ≤ i ≤ N - 1$). Here $\left\lfloor x \right\rfloor$ is the largest integer which is smaller than or equal to $x$. |
| 7 | 26 | No additional constraints. |
4 3 4 1 2 1 2 2 3 3 4
3
If we perform the cat exercises in the following way, the cat moves 3ドル$ times in total.
Since there is no way to perform cat exercises where the cat moves more than or equal to 4ドル$ times from towers to adjacent towers, output 3ドル$.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 7.
7 3 2 7 1 5 4 6 1 2 1 3 2 4 2 5 3 6 3 7
7
This sample input satisfies the constraints of Subtasks 4, 6, 7.