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

\(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\) つのタワーを選んでそこに障害物を置く操作の繰り返しである． ただし，既に障害物を置いたタワーに再び障害物を置くことはできない． 操作によって以下のことが起こる．

• 選んだタワーに猫がいない場合，何も起こらない．
• 選んだタワーに猫がおり，かつそれに隣接するタワーすべてに障害物が置かれている場合，キャットエクササイズが終了する．
• いずれでもない場合，障害物が置かれていない隣接するタワーへの移動を繰り返して選んだタワーから移動できるタワーのうち，選んだタワーを除いて最も高いタワーへ，隣接するタワーへの移動を繰り返すことで猫が移動する．このとき，猫は隣接するタワーへの移動の回数が最小になるように移動する．

タワーの高さと隣接するタワーの組の情報が与えられたとき， 障害物の置き方を工夫したときの，猫が隣接するタワーへ移動する回数の合計の最大値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

\(N\)
\(P_1\) \(P_2\) \(\cdots\) \(P_N\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
\(\vdots\)
\(A_{N-1}\) \(B_{N-1}\)

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

• \(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\))．
• はじめ，どのタワーからどのタワーへも隣接するタワーへ移動する操作を繰り返して移動できる．
• 入力される値はすべて整数である．

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\) 点) 追加の制約はない．

JOI 2023 · JCIOI · CC BY-SA 4.0