問題一覧 > 通常問題

No.364 門松木

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

問題文

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

  • A1,A2,A3 は全て異なる
  • 3 つの要素の中で A2 が最も大きい、または、A2 が最も小さい

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

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


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

  1. 木が門松木でなかった場合、 0 点とする。
  2. 木が門松木であった場合、門松木に含まれる門松列の数をその点数とする。
    次数 2 以上の 1 つの頂点をvvに隣接する2つの頂点をu,w(uw)として、 数列 Au,Av,Aw が門松列になるとき、 頂点の組{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が値Aiを持つ木です。
この木の部分木を1つ門松木品評会に出展しようと考えています。
かど松さんが品評会で得られる最大の点数を答えてください。出展できる木は1つだけであることに注意して下さい。

入力

N
A1 A2  AN
x1 y1
x2 y2

xn1 yn1

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

入力は全て整数で、以下の制約を満たします。
1N5×104
1Ai103
1xi,yiN
xiyi
木に多重辺や自己ループはなく、連結であることが保証されます。

出力

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

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。