問題一覧 > 通常問題

No.364 門松木

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : koyumeishikoyumeishi / テスター : uwiuwi
1 ProblemId : 1009 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:33:33

問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。

  • $A_1, A_2, A_3$ は全て異なる
  • $3$ つの要素の中で $A_2$ が最も大きい、または、$A_2$ が最も小さい

頂点$i$が値$A_i$を持つ木が次を満たすとき、この木は門松木であるといいます。

  • 次数 2 以上の 1 つの頂点を$v$、$v$に隣接する2つの頂点を$u,w$($u \neq w$)としたとき、 全ての$u,v,w$について、数列 $A_u, A_v, A_w$ が門松列である
    (どの連続する3頂点$u,v,w$を取り出しても、数列 $A_u, A_v, A_w$ が門松列である、と言い換えてもよい)
例えば、下図の左の木はどのように$u,v,w$を選んでも門松列になるので門松木ですが、 右の木は $u,v,w=3,2,4$ のとき、 $A_3, A_2, A_4 = 2, 6, 2$ が門松列にならないので門松木ではありません。 (丸の中の黒字が頂点番号、丸の外の色付きの数が頂点の値)


不定期に開催される門松木品評会では、木を次のように点数化し評価します。

  1. 木が門松木でなかった場合、 0 点とする。
  2. 木が門松木であった場合、門松木に含まれる門松列の数をその点数とする。
    次数 2 以上の 1 つの頂点を$v$、$v$に隣接する2つの頂点を$u,w(u \neq w)$として、 数列 $A_u, A_v, A_w$ が門松列になるとき、 頂点の組$\{u,v,w\}$を1つの門松列としてカウントする。 ただし、$\{u,v,w\}$と$\{w,v,u\}$は同一であるとみなし、重複してカウントしない。
例えば、下図の左の木は $\{2,1,5\}, \{3,2,1\}, \{3,2,4\}, \{4,2,1\}$ の計4つの門松列が含まれるので 4 点、 右の木は $\{3,2,4\}$ が門松列にならないのでこの木は門松木ではなく、 0 点となります。


かど松さんは木を1つ所有しています。 $N$頂点で、頂点$i$が値$A_i$を持つ木です。
この木の部分木を1つ門松木品評会に出展しようと考えています。
かど松さんが品評会で得られる最大の点数を答えてください。出展できる木は1つだけであることに注意して下さい。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{n-1}$ $y_{n-1}$

1行目に木の頂点数 $N$ が与えられます。
2行目に頂点 $i$ の持つ値 $A_i$ が空白区切りで与えられます。
3行目以降$N-1$行に、辺の情報が与えられます。 $i$番目の辺は頂点$x_i$ と 頂点$y_i$を結ぶ辺です。

入力は全て整数で、以下の制約を満たします。
$1 \leq N \leq 5 \times 10^4$
$1 \leq A_i \leq 10^3$
$1 \leq x_i,y_i \leq N$
$x_i \neq y_i$
木に多重辺や自己ループはなく、連結であることが保証されます。

出力

かど松さんが得られる点数の最大値を出力して下さい。

サンプル

サンプル1
入力
5
1 6 3 2 3
1 2
2 3
2 4
1 5
出力
4

問題文の図の左の木の例です。元々門松木なので、そのまま出展しましょう。

サンプル2
入力
5
1 6 2 2 3
1 2
2 3
2 4
1 5
出力
2

問題文の図の右の木の例です。値2を持つ頂点の片方を取り除いたとき、点数は最大になります。

サンプル3
入力
6
1 2 1 2 1 2
1 2
2 3
3 4
4 5
5 6
出力
0

[1]-[2] のような部分木は定義から門松木ですが、 木に門松列を含まないので結局 0 点です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。