K問題 - Bully Dunsparce

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

\(0\)から\(N-1\)までの番号が付けられた\(N\)部屋があります。部屋\(i \quad (0 \leq i \leq N-1)\)の気温は整数\(T_i\)で与えられます。 また、\(0 \leq j \leq N-2\)を満たす整数\(j\)に対して、 部屋\(A_j\)と部屋\(B_j\)が隣接しています。(\(N-1\)組の部屋が隣接しています。)

AくんはBくんから預かったペットのツチノコであるDunsparceをこの部屋たちを使っていじめて遊ぶことにしました。

AくんとDunsparceは以下の行動をします。ただし、はじめDunsparceは部屋\(0\)にいます。

行動

1. Dunsparceは以下の移動規則に従って移動を開始する。
2. Dunsparceの移動が終了すると、Aくんは封鎖されていない部屋を1つ選んで封鎖する。
   • 全ての部屋が封鎖されている、またはどの部屋を選んでもDunsparceが移動を終了するとき、AくんとDunsparceは行動を止める。
3. 1.に戻る。

移動規則

• 今いる部屋の番号を\(i\)とする。
• 部屋\(i\)から部屋\(j\)への移動は、以下の条件がすべて満たされるとき、することができる。
  • \(i \neq j\)
  • 部屋\(i,j\)ともに封鎖されていない。
  • 部屋\(i\)と部屋\(i\)に隣接した部屋の集合を\(S\)とするとき、\(\displaystyle T_j = \max_{k \in S}{T_k}\)が成立する。
• 今いる部屋から移動できる部屋がないとき(今いる部屋\(i\)に対して上の条件を満たす\(j\)が存在しないとき)、Dunsparceの移動は終了する。

ただし、行動を始める前にAくんは部屋\(0\)を除く好きな部屋をあらかじめ好きなだけ封鎖しておくことができます。

ここで配列\(P\)を、「上記の行動に従って移動したDunsparceがいた部屋の気温を、(Dunsparceがはじめにいた)部屋\(0\)の気温\(T_0\)を先頭に移動した順番に記録した配列」とします。

\(\displaystyle \sum_{k=0}^{n(P)-2}|P_i - P_{i+1}|\)を最大化するようにDunsparceが移動したとき、その値はいくつになるかを求めてください。

\(n(A)\)は配列の大きさ(=要素数)を表します。

例えば、\(B=[1,2,3]\)のとき\(n(B)=3\)です。

制約

• \(2 \leq N \leq 2 \times 10^5\)
• \(0 \leq A_j, B_j \leq N-1, \; A_j \neq B_j \quad (0 \leq j \leq N-2)\)
• \(0 \leq T_i \leq 10^9 \quad (0 \leq i \leq N-1)\)
• \(T_i \neq T_j \quad (0 \leq i < j \leq N-1)\)
• はじめ、どの部屋からどの部屋へも隣接する部屋へ移動する操作を繰り返して移動できる。
• 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

N
T_0 T_1 T_2 ... T_{N-1}
A_0 B_0
A_1 B_1
...
A_{N-2} B_{N-2}

出力

標準出力に、求める値を1行で出力してください。

入力例1

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

出力例1

27

あらかじめ部屋は封鎖しません。そして\(6 \rightarrow 3 \rightarrow 2 \rightarrow 0 \rightarrow 5 \rightarrow 4 \rightarrow 1\) の順で部屋を封鎖するとDunsparceは \(0 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 0 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 5 \rightarrow 1 \rightarrow 4 \rightarrow 1\) と移動するため、 \(|1-5|+|5-6|+|6-5|+|5-1|+|1-2|+|2-1|+|1-0|+|0-4|+|4-0|+|0-3|+|3-0|\) \(=4+1+1+4+1+1+1+4+4+3+3\) \(=27\)となり、スコアはこの時最大になるため、27を出力します。