AT_agc007_e [AGC007E] Shik and Travel

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_e ある国には $ N $ 個の都市があり、それらは $ N-1 $ 本の道路で結ばれています。道路は双方向に通行できます。便宜上、都市には $ 1 $ から $ N $ の、道路には $ 1 $ から $ N-1 $ の番号が振られています。グラフ理論の用語を用いると、任意の二つの都市に対し、それらを結ぶ単純道がちょうど一つ存在します。すなわち、都市と道路から構成されるグラフは木です。また、$ 1 $ 番の都市をこの木の根とみなすと、この木は全二分木となっています。（全二分木とは、葉以外の任意の頂点がちょうど二つの子を持つような根付き木のことをいいます。）$ i $ 番の道路は $ i+1 $ 番の都市と $ a_i $ 番の都市を結び、一回の通行ごとに $ v_i $ の通行料が発生します。（$ v_i $ が $ 0 $ であるような道路では通行料は発生しません。） $ 1 $ 番の都市に、社員の旅行を奨励していることで有名な会社があります。この会社には道路通行料補助制度という制度があり、社員の旅行中に発生する道路の通行料のほとんどを会社が負担します。旅行がこの制度の適用対象となるためにはいくつかの制約を満たす必要があり、その範囲内であれば好きなように旅程を決めることができます。これらの詳細は以下の通りです。 - 制度の適用対象となるためには、旅行の出発点と終着点はともに $ 1 $ 番の都市でなければならない。また、この国の都市と道路を $ 1 $ 番の都市を根とする根付き木とみなしたとき、この木の葉の個数を $ m $ とすると、旅行日程は $ m $ 泊 $ m+1 $ 日でなければならない。これらの $ m $ 回の宿泊は、木の葉に相当する都市のすべてで一度ずつ行わなければならない。 - 旅行全体を通じて、この国のすべての道路をそれぞれちょうど二度ずつ通行しなければならない。 - 旅行中に発生する道路の通行料のうち、社員自身が負担しなければならない金額は、発生する通行料の合計が最大であるような日（ただし旅行初日および最終日を除く）に発生する通行料の合計である。残りの金額は会社の負担となる。 シックはこの会社の従業員です。道路通行料補助制度のもとで行う今度の旅行では、発生する通行料のうち自分自身で支払わなければならない金額を最小にすることだけを考えています。そのような旅程を組む手伝いをしてあげてください。

N/A

N/A

### 制約 - $ 2\