← 返回题目列表

AtCoder · arc160_e

E. 建立双连接

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

分数: 800 点

问题陈述

给你一棵无向树 G 与 N 顶点。 每个顶点的度数 G 最多是 3.
顶点已编号 1 to N。边缘已编号 1 to N-1,和边缘 i 连接顶点 u_i 和顶点 v_i.
每个顶点都有固定的权重,顶点的权重 i is W_i.

您将添加零个或多个边 G。在顶点之间添加边的成本 i 和顶点 j is W_i + W_j.

打印一种添加边缘的方法,以满足以下条件,从而尽可能降低总成本。

  • G is 2-顶点连接。换句话说,对于每个顶点 v in G,删除 v 及其入射边 G 不会断开连接 G.

你有 T 测试用例解决。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • 给定的图是一棵树。
  • 给定图中每个顶点的度数最多为 3.
  • 1 \leq W_i \leq 10^9
  • W_i 是一个整数。
  • 总和 N 测试用例最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 代表 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_N

每个测试用例均采用以下格式:

N 
W_1 W_2 \dots W_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

输出

对于每个测试用例,按以下格式打印解决方案,其中:

  • M 是添加的边数,并且
  • 这 i- 添加的第一条边连接顶点 a_i 和顶点 b_i.

如果存在多个解决方案,则其中任何一个都将被接受。

M 
a_1 b_1
a_2 b_2
\vdots
a_M b_M

示例输入 1

2
3
2 3 5
1 2
2 3
7
1 10 100 1000 10000 100000 1000000
1 2
2 3
2 4
3 5
3 6
4 7

示例输出 1

1
1 3
2
7 6
1 5

在第一个测试用例中,添加一条连接顶点的边 1 和顶点 3 使 G 满足问题陈述中的条件。
其成本是 W_1 + W_3 = 2 + 5 = 7。 没有办法以小于的成本添加边来满足条件 7,所以这是一个有效的解决方案。

在第二个测试用例中,上述解决方案的总成本为 (W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001,这是可能的最小值。