AT_pakencamp_2025_day1_q Reconstruct

$ \mathrm{TESTCASES} $ 個のテストケースについて、次の問題を解いてください。 頂点 $ 1, 2 \ldots N $ からなる $ N $ 頂点の木 $ \mathrm{T} $ が与えられます。 $ \mathrm{T} $ の辺のうち $ i $ 番目の辺は頂点 $ U_i $ と $ V_i $ を結びます。 パンダのパ太郎は次のような操作をちょうど $ 1 $ 回行います： - 操作 $ 1. $ $ \mathrm{T} $ の辺を $ 1 $ つ選び削除する - 操作 $ 2. $ 操作 $ 1 $ の結果非連結となった $ 2 $ つの連結成分から、頂点 $ a,b $ をそれぞれ $ 1 $ つずつ選び、それらの間に辺を追加して再び $ 1 $ つの木にする。 操作後の木における全頂点対間の距離の総和として考えられるもののうち、最小値を求めてください。

入力は以下の形式で標準入力から与えられる。入力の $ 1 $ 行目は以下の形式である。 > $ \mathrm{TESTCASES} $ その後、 $ \mathrm{TESTCASES} $ 個のテストケースが続く。各テストケースは以下の形式で与えられる。 > $ N $ $ U_1 $ $ V_1 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $

操作後の木の全頂点対間の距離の総和として考えられる値の最小値を $ 1 $ 行で出力せよ。

### 部分点 次の追加制約を満たすテストケースに正解した場合、 $ 300 $ 点が与えられる。 - 各テストケースにおける $ N^2 $ の総和は $ {10}^{7} $ 以下である ### Sample Explanation 1 この例では、 $ 3 $ つのテストケースが存在します。 $ 1 $ つ目のテストケースでは、操作 $ 1 $ で辺 $ (1,3) $ を削除し、操作 $ 2 $ で辺 $ (2,3) $ を追加することで最小値 $ 16 $ を達成することができます。 このとき、操作後の $ \mathrm{T} $ の辺は、 $ (1,2) $ , $ (2,3) $ , $ (2,4) $ , $ (2,5) $ の $ 4 $ 本です。 $ 2 $ つ目のテストケースについて、操作 $ 2 $ で追加した辺は操作 $ 1 $ で削除した辺と同一なものであっても構わないことに注意してください。 ### Constraints - $ 2 \leq \mathrm{TESTCASES} \leq {10}^{5} $ - $ 2 \leq N \leq 2 \times {10}^{5} $ - $ 1 \leq U_i \lt V_i \leq N $ - 与えられるグラフは木である - 各テストケースにおける $ N $ の総和は $ 2 \times {10}^{5} $ 以下である - 入力は全て整数