← 返回题目列表

AtCoder · pakencamp_2025_day1_q

Q. 重建

中文机器翻译题面 查看原题

配点 : 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 删除的边相同。