配点 : 600 点
問題文
\mathrm{TESTCASES} 测试用例的以下问题。 包括
頂点 1, 2 \ldots N 组成 N 顶点树 在 \mathrm{T} 。 将\mathrm{T} 的侧面之间 连接 i 第一条边是顶点 U_i 和 V_i 。 Panda Pataro 只是执行以下操作: 执行 1 次:
- 操作 1. \mathrm{T} 侧面 1 选择并删除
- 操作 2. 操作 1 导致未合并 2 从两个连接的组件中,顶点 a,b 分别 1 将它们一一选择,在它们之间添加一条边,然后重试。 1 将其变成一棵树。
求操作后树中所有顶点对之间距离的最小可能总和。
制約
- 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} 小于或等于
- 所有输入均为整数
部分点
如果满足以下附加约束的测试用例得到正确回答,300 点。
- 在每个测试用例中 N^2 的总和是 {10}^{7} 小于或等于
入力
输入是按以下格式从标准输入给出的。输入的 1 行具有以下格式。
\mathrm{TESTCASES}
然后,\mathrm{TESTCASES} 测试用例如下。每个测试用例均按以下格式给出。
N
U_1 V_1
\vdots
U_{N-1} V_{N-1}
出力
操作后树中所有顶点对之间的距离之和的最小值为 1 行。
入力例 1
3 5 1 2 1 3 2 4 2 5 2 1 2 10 1 2 2 3 2 4 3 6 3 9 3 10 4 5 5 7 7 8
出力例 1
16 1 105
在此示例中, 有3 测试用例。 1 在第二个测试用例中,操作 1 删除 (1,3) 并操作 添加 2 删除 (2,3) 的最小值 16 可以实现。 此时,手术后 \mathrm{T} 的边是(1,2), (2,3), (2,4), (2,5) 的 4 这是一本书。
2 对于第二个测试用例,操作 添加了 2 的边被操纵。 请注意,它可能与您使用 1 删除的边相同。