各辺について，その辺がスコアに加算される回数を考えます． その辺を切ってできる\(2\)つの部分木のうち小さい方の大きさが上界です．

実はこの上界を達成することができます． まず，入力の木を重心 \(R\) を根として根付き木にします． 根の直接の子を \(v_1,v_2,\cdots,v_k\)，それらの部分木を \(T_1,T_2,\cdots,T_k\) とおきます． 最後の操作を除き，\(2\) つの異なる部分木から葉を選んで消すように操作できれば良いです．

最初，根のマッチング先が \(v_1\) だったとします． すると最初の操作では，\(T_1\) と \(T_j\) (\(j \neq 1\)) の葉を選ぶ必要があります． この操作の後，根のマッチング先は \(v_j\) になります．そこで今度は \(T_j\) を選び…と操作が続いていきます． ここで，\(T_j\) を選ぶ際にサイズが最も大きい \(T_j\) を選ぶようにすると，操作を最後まで完了することができます． ただしここでは，各部分木の頂点数がvalidであることだけを保証しており，葉をうまく取れるかどうかはわかりません．

このように述べましたが，実は各部分木内で葉を取ることができます． これは部分木の根から順番に考えれば良いです． 今ある頂点 \(v\) に注目しているとします． もし \(v\) とマッチしている頂点が \(v\) の子であるなら，その子の部分木内の葉を選ぶ必要があります． そうでないなら，適当な子を選んでその部分木から葉を選ぶことにすればよいです． この操作を続けるといずれ葉に到達するので，この葉を削除する操作を行えばよいです．

適切な葉を取る手順を説明しましたが，葉を一個ずつ取ることにすると最悪の場合計算量が全体で \(O(N^2)\) になってしまいます． しかし，上の手順を少し応用することで，各頂点を葉として取っていくうまい順序を見つけることができます． 具体的には，マッチングに使われている辺を優先的に使うような dfs を行い，その帰りがけ順に頂点を使えばよいです．

以上の操作を実装すれば，この問題は \(O(N\log N)\) 時間で解けます．

回答例(C++)