AT_joi2023ho_d キャットエクササイズ (Cat Exercise)
Description
$ N $ 個のキャットタワーがあり，それぞれに $ 1 $ から $ N $ までの番号が付けられている． タワー $ i $ ( $ 1 \leqq i \leqq N $ ) の高さは $ P_i $ である． タワーの高さは $ 1 $ 以上 $ N $ 以下の相異なる整数である． $ N-1 $ 組のタワーが隣接しており，各 $ j $ ( $ 1 \leqq j \leqq N-1 $ ) について， タワー $ A_j $ とタワー $ B_j $ が隣接している． はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．
最初，猫が高さ $ N $ のタワーの上にいる．
次に，**キャットエクササイズ**を行う． キャットエクササイズとは， $ 1 $ つのタワーを選んでそこに障害物を置く操作の繰り返しである． ただし，既に障害物を置いたタワーに再び障害物を置くことはできない． 操作によって以下のことが起こる．
- 選んだタワーに猫がいない場合，何も起こらない．
- 選んだタワーに猫がおり，かつそれに隣接するタワーすべてに障害物が置かれている場合，キャットエクササイズが終了する．
- いずれでもない場合，障害物が置かれていない隣接するタワーへの移動を繰り返して選んだタワーから移動できるタワーのうち，選んだタワーを除いて最も高いタワーへ，隣接するタワーへの移動を繰り返すことで猫が移動する．このとき，猫は隣接するタワーへの移動の回数が最小になるように移動する．
タワーの高さと隣接するタワーの組の情報が与えられたとき， 障害物の置き方を工夫したときの，猫が隣接するタワーへ移動する回数の合計の最大値を求めるプログラムを作成せよ．
---
Input Format
入力は以下の形式で標準入力から与えられる．
> $ N $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $
Output Format
標準出力に，猫が隣接するタワーへ移動する回数の合計の最大値を $ 1 $ 行で出力せよ．
---
Explanation/Hint
### 小課題
1. ( $ 7 $ 点) $ A_i=i $ ， $ B_i=i+1 $ ( $ 1 \leqq i \leqq N-1 $ )， $ N \leqq 16 $ ．
2. ( $ 7 $ 点) $ A_i=i $ ， $ B_i=i+1 $ ( $ 1 \leqq i \leqq N-1 $ )， $ N \leqq 300 $ ．
3. ( $ 7 $ 点) $ A_i=i $ ， $ B_i=i+1 $ ( $ 1 \leqq i \leqq N-1 $ )， $ N \leqq 5\,000 $ ．
4. ( $ 10 $ 点) $ N \leqq 5\,000 $ ．
5. ( $ 20 $ 点) $ A_i=i $ ， $ B_i=i+1 $ ( $ 1 \leqq i \leqq N-1 $ )．
6. ( $ 23 $ 点) $ A_i=\left\lfloor \frac{i+1}{2} \right\rfloor $ ， $ B_i=i+1 $ ( $ 1 \leqq i \leqq N-1 $ )．ただし， $ \lfloor x \rfloor $ は $ x $ の小数点以下を切り捨てた値を表す．
7. ( $ 26 $ 点) 追加の制約はない．
---
### Sample Explanation 1
以下のようにキャットエクササイズを行ったとき，猫は合計 $ 3 $ 回移動する．
- タワー $ 1 $ に障害物を置く．このとき，猫は移動しない．
- タワー $ 2 $ に障害物を置く．このとき，猫はタワー $ 2 $ からタワー $ 3 $ へ移動し，続いてタワー $ 3 $ からタワー $ 4 $ へと移動する．
- タワー $ 4 $ に障害物を置く．このとき，猫はタワー $ 4 $ からタワー $ 3 $ へと移動する．
- タワー $ 3 $ に障害物を置く．ここでキャットエクササイズが終了する．
猫が $ 4 $ 回以上隣接するタワーへの移動を行うキャットエクササイズの方法は存在しないため， $ 3 $ を出力する．
この入力例は小課題 $ 1,2,3,4,5,7 $ の制約を満たす．
---
### Sample Explanation 2
この入力例は小課題 $ 4,6,7 $ の制約を満たす．
### Constraints
- $ 2 \leqq N \leqq 200\,000 $ ．
- $ 1 \leqq P_i \leqq N $ ( $ 1 \leqq i \leqq N $ )．
- $ P_i \neq P_j $ ( $ 1 \leqq i < j \leqq N $ )．
- $ 1 \leqq A_j < B_j \leqq N $ ( $ 1 \leqq j \leqq N-1 $ )．
- はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．
- 入力される値はすべて整数である．