キャットエクササイズ(Cat Exercise)

N 個のキャットタワーがあり,それぞれに1 からN までの番号が付けられている.タワーi (1 ≦i ≦N)
の高さはPi である.タワーの高さは1 以上N 以下の相異なる整数である.N −1 組のタワーが隣接してお
り,各j (1 ≦j ≦N −1) について,タワーAj とタワーBj が隣接している.はじめ,どのタワーからどのタ
ワーへも隣接するタワーへ移動する操作を繰り返して移動できる.
最初,猫が高さN のタワーの上にいる.
次に,キャットエクササイズを行う.キャットエクササイズとは,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. (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 点) Ai =
   ⌊i+1
   2
   ⌋
   ,Bi = i + 1 (1 ≦i ≦N −1).ただし,⌊x⌋はx の小数点以下を切り捨てた値を表す.
7. (26 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N
P1 P2 · · · PN
A1 B1
A2 B2
...
AN−1 BN−1

第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)

標準出力に,猫が隣接するタワーへ移動する回数の合計の最大値を1 行で出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2023 Final