E - Make Biconnected Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

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 のコストがかかります。

次の条件を満たすように辺を追加する方法のうち、コストの総和が最小である方法を 1 つ出力してください。

  • G は二重頂点連結である。つまり、G 内の任意の頂点 v について、G から頂点 v および v に隣接する辺を取り除いても 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 番目のテストケースでは、頂点 1 と頂点 3 を結ぶ辺を張ると G が問題文の条件を満たします。
この時、コストは W_1 + W_3 = 2 + 5 = 7 になります。 コストが 7 未満で条件を満たす辺の張り方は存在しないため、これが答えになります。

2 番目のテストケースでは、コストの総和は (W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001 になり、これが最小です。

Score : 800 points

Problem Statement

You are given an undirected tree G with N vertices. The degree of every vertex in G is at most 3.
The vertices are numbered 1 to N. The edges are numbered 1 to N-1, and edge i connects vertex u_i and vertex v_i.
Each vertex has a fixed weight, and the weight of vertex i is W_i.

You will add zero or more edges to G. The cost of adding an edge between vertex i and vertex j is W_i + W_j.

Print one way to add edges to satisfy the following condition for the minimum possible total cost.

  • G is 2-vertex-connected. In other words, for every vertex v in G, removing v and its incident edges from G would not disconnect G.

You have T test cases to solve.

Constraints

  • 1 \leq T \leq 2 \times 10^5
  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • The given graph is a tree.
  • The degree of every vertex in the given graph is at most 3.
  • 1 \leq W_i \leq 10^9
  • W_i is an integer.
  • The sum of N across the test cases is at most 2 \times 10^5.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i represents the i-th test case:

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

Each test case is in the following format:

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

Output

For each test case, print a solution in the following format, where:

  • M is the number of added edges, and
  • the i-th added edge connects vertex a_i and vertex b_i.

If multiple solutions exist, any of them would be accepted.

M 
a_1 b_1
a_2 b_2
\vdots
a_M b_M

Sample Input 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

Sample Output 1

1
1 3
2
7 6
1 5

In the first test case, adding an edge connecting vertex 1 and vertex 3 makes G satisfy the condition in the problem statement.
The cost of this is W_1 + W_3 = 2 + 5 = 7. There is no way to add edges to satisfy the condition for a cost of less than 7, so this is a valid solution.

In the second test case, the solution above has a total cost of (W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001, which is the minimum possible.