题目描述

There are $N$ cat towers, numbered from $1$ to $N$. The height of Tower $i$ ($1 \le i \le 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 \le j \le 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$ $B_N$

输出格式

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.

题目大意

有 $N$ 个猫爬架，编号从 $1$ 到 $N$。第 $i$（$1 \le i \le N$）个架子的高度是 $P_i$。架子的高度是 $1$ 和 $N$ 之间的不同整数，包括 $1$ 和 $N$。有 $N - 1$ 对架子彼此相邻。对于每个 $j$（$1 \le j \le N-1$），第 $A_j$ 个架子和第 $B_j$ 个架子彼此相邻。从任意一个架子开始，总能通过不断移动到相邻的架子来到达所有其它架子。

一开始，一只猫待在高度为 $N$ 的那个架子中。

接下来对这只猫进行锻炼。在锻炼中，我们每次选择一个架子并在其上放置障碍物。但是，我们不能在已经放置障碍物的架子上再放置障碍物。在此过程中，会发生以下情况。

• 如果猫不待在选定的架子中，则什么也不会发生。
• 如果猫待在选定的架子中，并且与选定架子相邻的每个架子上都有障碍物，则锻炼结束。
• 否则，猫将沿最短路径前往，仅通过移动到相邻的架子且不经过放置过障碍物的架子，能到达的所有架子中，高度最高的那个。

给定每个架子的高度和架子彼此相邻的方式，编写一个程序，计算如果我们适当放置障碍物，猫最多需要移动多少次。从一个架子移动到相邻的架子被称为一次移动。

4
3 4 1 2
1 2
2 3
3 4

3

7
3 2 7 1 5 4 6
1 2
1 3
2 4
2 5
3 6
3 7

7

提示

Samples

Sample 1

If we perform the cat exercises in the following way, the cat moves 3 times in total.

• We put an obstacle on Tower 1. The cat does not move.
• We put an obstacle on Tower 2. The cat moves from Tower 2 to Tower 3. Then, the cat moves from Tower 3 to Tower 4.
• We put an obstacle on Tower 4. The cat moves from Tower 4 to Tower 3.
• We put an obstacle on Tower 3. Then the cat exercises finish.

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.

Sample 2

This sample input satisfies the constraints of Subtasks 4, 6, 7.

Constraints

• $2 \le N \le 2\times 10^5$.
• $1 \le P_i \le N$ ($1 \le i \le N$).
• $P_i \neq P_j$ ($1 \le i < j \le N$).
• $1 \le A_j < B_j \le N$ ($1 \le j \le 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.

Subtasks

1. (7 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$), $N \le 16$．
2. (7 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$), $N \le 300$．
3. (7 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$), $N \le 5 000$．
4. (10 points) $N \le 5 000$．
5. (20 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)．
6. (23 points) $A_i =\left\lfloor\frac{i+1}2\right\rfloor, B_i = i + 1$ ($1 \le i \le N - 1$). Here $\lfloor x \rfloor$ is the largest integer which is smaller than or equal to $x$.
7. (26 points) No additional constraints.