← 返回题目列表

Codeforces · 1935/F

F. 安德烈的树

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

安德烈大师非常喜欢树$$$^{\dagger}$$$,所以他有一棵由$$$n$$$顶点组成的树。

但事情没那么简单。蒂莫菲大师决定从树上偷一个顶点。如果 Timofey 从树中窃取了顶点 $$$v$$$,则顶点 $$$v$$$ 以及一端位于顶点 $$$v$$$ 的所有边都会从树中删除,而其他顶点的数量保持不变。为了防止安德烈生气,蒂莫菲决定再次将生成的图变成树。为此,他可以在任意顶点$$$a$$$和$$$b$$$之间添加边,但是添加这样的边时,他必须向大师援助中心支付$$$|a - b|$$$硬币。

请注意,生成的树不包含顶点 $$$v$$$。

Timofey 尚未决定从树中删除哪个顶点 $$$v$$$,因此他想知道对于每个顶点 $$$1 \leq v \leq n$$$,删除顶点 $$$v$$$ 后使图再次成为树所需的最少硬币数,以及需要添加哪些边。

$$$^{\dagger}$$$树是无环的无向连通图。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$5 \le n \le 2\cdot10^5$$$) — Andrey 树中的顶点数。

接下来的 $$$n - 1$$$ 行包含树边缘的描述。这些行的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — 由第 $$$i$$$ 条边连接的顶点数。

保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,按以下格式输出答案:

对于每个顶点$$$v$$$(按照从$$$1$$$到$$$n$$$的顺序),在第一行输出两个整数$$$w$$$和$$$m$$$——删除顶点$$$v$$$后使图再次成为树所需花费的最小硬币数量,以及添加的边的数量。

然后输出 $$$m$$$ 行,每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n, a \ne v, b \ne v$$$, $$$a \ne b$$$) — 添加边的末端。

如果有多种添加边的方法,则可以以最小的成本输出任何解决方案。

示例

输入 #1

3
5
1 3
1 4
4 5
3 2
5
4 2
4 3
3 5
5 1
5
2 1
1 5
1 4
1 3

输出 #1

1 1
3 4

0 0

1 1
1 2

2 1
3 5

0 0

0 0

0 0

1 1
1 2

1 1
1 2

1 1
1 2

3 3
2 3
4 5
3 4

0 0

0 0

0 0

0 0

注意

在第一个测试用例中:

考虑删除顶点 $$$4$$$:

最佳解决方案是添加一条从顶点 $$$5$$$ 到顶点 $$$3$$$ 的边。那么我们将花费 $$$|5 - 3| = 2$$$ 硬币。

在第三个测试用例中:

考虑删除顶点$$$1$$$:

最佳解决方案是:

- 添加一条从顶点 $$$2$$$ 到顶点 $$$3$$$ 的边,花费 $$$|2 - 3| = 1$$$ 硬币。
- 添加一条从顶点 $$$3$$$ 到顶点 $$$4$$$ 的边,花费 $$$|3 - 4| = 1$$$ 硬币。
- 添加一条从顶点 $$$4$$$ 到顶点 $$$5$$$ 的边,花费 $$$|4 - 5| = 1$$$ 硬币。

那么我们总共会花费 $$$1 + 1 + 1 = 3$$$ 币。

考虑删除顶点 $$$2$$$:

不需要添加边,因为删除顶点后图仍将是一棵树。