AT_agc025_e [AGC025E] Walking on a Tree

[problemUrl]: https://atcoder.jp/contests/agc025/tasks/agc025_e 高橋君は木上を散歩するのが大好きです。 高橋君が散歩をする木は $ N $ 頂点からなり、各頂点には $ 1 $ から $ N $ の番号が割り振られています。 また、$ N-1 $ 本の辺のうち、$ i $ 本目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 高橋君は $ M $ 回の散歩の予定を組みました。$ i $ 回目の散歩は以下のようにして行う予定です。 - $ 2 $ つの頂点 $ u_i,v_i $ が決まっている。 - 高橋君は頂点 $ u_i $ から頂点 $ v_i $、または、頂点 $ v_i $ から頂点 $ u_i $ に向かって、同じ辺は一度しか通らないように移動する。 また、$ i $ 回目の散歩で得られる *楽しさ* は以下のように定義されています。 - $ i $ 回目の散歩で通った辺であって、以下のいずれかの条件を満たすものの個数 - 今回の散歩で初めて通った辺 - 今まで通ったことがあっても、今回とは逆向きでしか通っていなかった辺 高橋君は $ M $ 回の散歩の楽しさの合計が最大になるように、各散歩の向きを決めたいです。 そこで、高橋君が得られる楽しさの合計の最大値と、実際に楽しさの合計が最大となる各散歩の向きの定め方の一例を求めてください。

N/A

N/A

### 制約 - $ 1\ ≦\ N,M\ ≦\ 2000 $ - $ 1\ ≦\ a_i\ ,\ b_i\ ≦\ N $ - $ 1\ ≦\ u_i\ ,\ v_i\ ≦\ N $ - $ a_i\ \neq\ b_i $ - $ u_i\ \neq\ v_i $ - 入力で与えられるグラフは木である。 ### Sample Explanation 1 上のように散歩の向きを定めると、各散歩で $ 2 $ ずつ楽しさを得ることができ、合計の楽しさが $ 6 $ になります。