分数: 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,这是可能的最小值。