AT_abc362_f [ABC362F] Perfect Matching on a Tree

[problemUrl]: https://atcoder.jp/contests/abc362/tasks/abc362_f $ N $ 頂点の木 $ T $ が与えられます。$ T $ の頂点には $ 1 $ から $ N $ の番号がついており、 $ i\,(1\leq\ i\ \leq\ N-1) $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでいます。 $ T $ を用いて、$ N $ 頂点の完全グラフ $ G $ を次のように定めます。 - $ G $ の頂点 $ x $ と頂点 $ y $ の間の辺の重み $ w(x,y) $ を、$ T $ における頂点 $ x $ と頂点 $ y $ の間の最短距離とする $ G $ の**最大重み最大マッチング**を一つ求めてください。すなわち、$ \lfloor\ N/2\ \rfloor $ 個の頂点のペアの集合 $ M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor\ N/2\ \rfloor},y_{\lfloor\ N/2\ \rfloor})\} $ であって、各頂点 $ 1,2,\dots,\ N $ が $ M $ に現れる回数がたかだか $ 1 $ 回であるようなもののうち、 $ \displaystyle\ \sum_{i=1}^{\lfloor\ N/2\ \rfloor}\ w(x_i,y_i) $ が最大であるものを一つ求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ u_i\