AT_pakencamp_2025_day1_q Reconstruct

请对 $ \mathrm{TESTCASES} $ 个测试用例分别解答下述问题。 给定一棵包含 $ 1,2,\ldots,N $ 共 $ N $ 个顶点的树 $ \mathrm{T} $。$ \mathrm{T} $ 的第 $ i $ 条边连接顶点 $ U_i $ 和 $ V_i $。Panda 的帕太郎会恰好进行如下两步操作一次： - 操作 1. 任选 $ \mathrm{T} $ 的一条边并将其删除； - 操作 2. 操作 1 后图变成了两个连通分量，分别在这两个分量中选择一个顶点 $ a,b $，在它们之间添加一条边，使图再次变为一棵树。 请你求出，经过操作后，所有顶点对间距离之和的最小可能值。

输入从标准输入读入。第 1 行格式如下： > $ \mathrm{TESTCASES} $ 接下来有 $ \mathrm{TESTCASES} $ 组测试数据。每组数据格式如下： > $ N $ > $ U_1 $ $ V_1 $ > $\vdots$ > $ U_{N-1} $ $ V_{N-1} $

请输出操作后所有顶点对间距离之和的最小可能值，每个测试用例一行。

### 部分得分 若你能正确解决满足下述额外限制的测试用例，将获得 $ 300 $ 分： - 所有测试用例的 $ N^2 $ 之和不超过 $ 10^7 $ ### 样例解释 1 本例共有 3 组测试数据。在第 1 组测试数据中，如果第 1 步删除 $(1,3)$ 这条边，第 2 步添加 $(2,3)$ 这条边，可以得到最小值 $ 16 $。此时操作后的树的边为 $(1,2)$、$(2,3)$、$(2,4)$、$(2,5)$ 共 4 条边。 对于第 2 组测试用例，请注意：第 2 步中添加的边可以与第 1 步移除的边相同。 ### 约束条件 - $ 2 \leq \mathrm{TESTCASES} \leq 10^5 $ - $ 2 \leq N \leq 2\times 10^5 $ - $ 1 \leq U_i < V_i \leq N $ - 输入保证给定图为一棵树 - 所有测试用例中 $ N $ 的总和不超过 $ 2\times 10^5 $ - 输入均为整数 由 ChatGPT 5 翻译