No.364 門松木
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 :
koyumeishi
/ テスター :
uwi
タグ : / 解いたユーザー数 19
作問者 :

問題文最終更新日: 2016-05-24 14:33:33
問題文
門松列 とは
は全て異なる つの要素の中で が最も大きい、または、 が最も小さい
頂点
-
次数 2 以上の 1 つの頂点を
、 に隣接する2つの頂点を ( )としたとき、 全ての について、数列 が門松列である
(どの連続する3頂点 を取り出しても、数列 が門松列である、と言い換えてもよい)
不定期に開催される門松木品評会では、木を次のように点数化し評価します。
- 木が門松木でなかった場合、 0 点とする。
- 木が門松木であった場合、門松木に含まれる門松列の数をその点数とする。
次数 2 以上の 1 つの頂点を 、 に隣接する2つの頂点を として、 数列 が門松列になるとき、 頂点の組 を1つの門松列としてカウントする。 ただし、 と は同一であるとみなし、重複してカウントしない。
かど松さんは木を1つ所有しています。
この木の部分木を1つ門松木品評会に出展しようと考えています。
かど松さんが品評会で得られる最大の点数を答えてください。出展できる木は1つだけであることに注意して下さい。
入力
1行目に木の頂点数
2行目に頂点
3行目以降
入力は全て整数で、以下の制約を満たします。
木に多重辺や自己ループはなく、連結であることが保証されます。
出力
かど松さんが得られる点数の最大値を出力して下さい。
サンプル
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。