AT_arc160_e [ARC160E] Make Biconnected

给定一棵有 $N$ 个顶点的无向树 $G$。**$G$ 的所有顶点的度数都不超过 $3$。** 顶点编号为 $1$ 到 $N$。边编号为 $1$ 到 $N-1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 此外，每个顶点都有一个权值，第 $i$ 个顶点的权值为 $W_i$。 你可以在 $G$ 上添加 $0$ 条或多条边。若在顶点 $i$ 和顶点 $j$ 之间添加一条边，则需要花费 $W_i + W_j$ 的代价。 请输出一种添加边的方法，使得满足以下条件，并且总代价最小： - $G$ 是二重顶点连通的。也就是说，对于 $G$ 中任意一个顶点 $v$，即使将 $v$ 及其所有相邻的边从 $G$ 中移除，$G$ 依然保持连通。 给定 $T$ 组测试数据，请分别输出每组的答案。

输入以如下格式从标准输入给出，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例。 > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每个测试用例的输入格式如下： > $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 \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$ ### 样例解释 1 在第 $1$ 个测试用例中，连接顶点 $1$ 和顶点 $3$ 可以使 $G$ 满足题目要求。此时总代价为 $W_1 + W_3 = 2 + 5 = 7$。不存在总代价小于 $7$ 且满足条件的方案，因此这是最优解。 在第 $2$ 个测试用例中，总代价为 $(W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001$，这是最小的。 由 ChatGPT 4.1 翻译