문제
N 개의 고양이 타워가 있으며 각각 1에서 N까지 번호가 매겨져 있습니다. 타워 i (1≤i≤N)의 높이는 Pi입니다. 타워의 높이는 1 이상 N 이하의 다른 정수입니다. N-1 세트의 타워가 인접하고 각 j (1≤j≤N-1)에 대해 타워 Aj와 타워 Bj가 인접합니다. 우선, 어느 타워로부터 어느 타워에 인접하는 타워로 이동하는 조작을 반복해서 이동할 수 있다.
처음에는 고양이가 높이 N의 타워 위에 있습니다.
그런 다음 고양이 운동을 합니다. 고양이 운동은 하나의 타워를 선택하고 거기에 장애물을 놓는 조작의 반복입니다. 그러나 이미 장애물이 있는 타워에 장애물을 다시 놓을 수는 없습니다. 조작에 의해 다음이 일어난다.
• 선택한 타워에 고양이가 없으면 아무 일도 일어나지 않습니다.
• 선택한 타워에 고양이가 있고 인접한 모든 타워에 장애물이 있는 경우 고양이 운동이 종료됩니다.
• 어느 쪽도 아닌 경우, 장애물이 놓여 있지 않은 인접한 타워로의 이동을 반복하여 선택한 타워로부터 이동할 수 있는 타워 중, 선택한 타워를 제외하고 가장 높은 타워로, 인접하는 타워로의 이동을 반복하면 고양이가 움직입니다. 이 때 고양이는 인접한 타워로의 이동 횟수가 최소가 되도록 이동합니다.
타워 높이와 인접한 타워 세트의 정보가 주어졌을 때 장애물을 놓는 방법을 고안했을 때 고양이가 인접한 타워로 이동하는 횟수의 합계의 최대치를 구하는 프로그램을 작성하라.
입력
입력은 다음 형식으로 표준 입력에서 제공됩니다.
N
P1 P2 · · · PN
A1 B1
A2 B2
.
.
.
AN-1 BN-1
[제한]
• 2 ≤ N ≤ 200 000.
• 1≤Pi≤N(1≤i≤N).
• Pi, Pj (1 ≤ i < j ≤ N).
• 1 ≤ Aj < Bj ≤ N (1 ≤ j ≤ N - 1).
• 처음에는 모든 타워에서 모든 타워에 인접한 타워로 이동하는 작업을 반복적으로 이동할 수 있습니다.
• 입력 된 모든 값은 정수입니다.
출력
표준 출력에 고양이가 인접한 타워로 이동하는 횟수의 합계의 최대치를 1행으로 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | Ai = i，Bi = i + 1 (1 ≦ i ≦ N − 1)，N ≦ 16． |
| #2 | 7점 | Ai = i，Bi = i + 1 (1 ≦ i ≦ N − 1)，N ≦ 300． |
| #3 | 7점 | Ai = i，Bi = i + 1 (1 ≦ i ≦ N − 1)，N ≦ 5 000 |
| #4 | 10점 | N ≦ 5 000 |
| #5 | 20점 | Ai = i，Bi = i + 1 (1 ≦ i ≦ N − 1) |
| #6 | 23점 | |
| #7 | 26점 | 추가 제한 없음 |
예제1
4
3412
12
23
34
3
다음과 같이 고양이 운동을 할 때 고양이는 총 3 번 움직입니다.
• 타워 1에 장애물을 놓습니다. 이 때 고양이는 움직이지 않습니다.
• 타워 2에 장애물을 놓습니다. 이 때 고양이는 타워 2에서 타워 3으로 이동 한 다음 타워 3에서
워 4로 이동한다.
• 타워 4에 장애물을 놓습니다. 이 때 고양이는 타워 4에서 타워 3으로 이동합니다.
• 타워 3에 장애물을 놓습니다. 이제 고양이 운동이 끝납니다.
고양이가 4회 이상 인접한 타워로 이동을 하는 고양이 운동의 방법은 존재하지 않기 때문에, 3을 출력
한다.
이 입력 예제는 작은 과제 1, 2, 3, 4, 5, 7의 제약 조건을 충족합니다.
예제2
7
3271546
12
13
24
25
36
37
7
이 입력 예는 작은 문제 4, 6, 7의 제약 조건을 충족합니다.