C - Double X 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 900 点

問題文

頂点に 1 から N の番号がついた N 頂点の木が 2 個与えられ、それぞれ T, U と呼びます。T の i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。U の i 番目の辺は頂点 b_i と頂点 c_i を結ぶ辺です。
また、長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

k = 1, 2, \dots, N に対して次の小問題を解いてください。

次の条件を満たす整数の組 (x_1, x_2, x_3, x_4) は存在しますか？また、存在する場合は条件を満たす組における \sum_{i=1}^4 A_{x_i} の最小値を求めてください。

  • x_1, x_2, x_3, x_4 は全て相異なる。
  • x_1, x_2, x_3, x_4 は全て k でない。
  • 1 \leq i \lt j \leq 4 を満たす全ての整数 (i,j) について、T 上の x_i x_j パスに頂点 k は載っていて、かつ U 上の x_i x_j パスにも頂点 k は載っている。

t 個のテストケースが与えられるので、それぞれについて問題を解いてください。

制約

  • 1 \leq t \leq 10^5
  • 5 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq u_i \lt v_i \leq N
  • 1 \leq b_i \lt c_i \leq N
  • T, U は木
  • 全てのテストケースに対する N の総和は 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。

t
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_t

各テストケースでは、入力は以下の形式で与えられる。

N
A_1 A_2 \dots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
b_1 c_1
b_2 c_2
\vdots
b_{N-1} c_{N-1}

出力

t 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。
各テストケースでは、小問題の答えを空白区切りで k=1,2,\dots,N の順に 1 行に出力せよ。
小問題では、条件を満たす整数の組 (x_1, x_2, x_3, x_4) が存在しない場合は -1 を、存在する場合はそのような組における \sum_{i=1}^4 A_{x_i} の最小値を出力せよ。

入力例 1

2
5
20 26 1 25 213
1 5
3 5
2 5
4 5
4 5
1 5
2 5
3 5
20
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288
1 2
2 3
1 4
1 5
2 6
3 7
3 8
3 9
2 10
1 11
8 12
6 13
5 14
11 15
13 16
1 17
7 18
9 19
15 20
1 2
2 3
2 4
4 5
2 6
1 7
6 8
3 9
3 10
7 11
7 12
1 13
3 14
3 15
8 16
1 17
3 18
2 19
1 20

出力例 1

-1 -1 -1 -1 72
70664 616 131968 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

1 番目のテストケースについて、k=1,2,3,4 の時は条件を満たす (x_1, x_2, x_3, x_4) は存在しません。また、k=5 の時は (x_1,x_2,x_3,x_4) = (1,2,3,4) が条件を満たします。

Score : 900 points

Problem Statement

You are given two trees T and U, each with N vertices numbered from 1 to N. The i-th edge of T connects vertices u_i and v_i. The i-th edge of U connects vertices b_i and c_i.
You are also given a length-N integer sequence A=(A_1,A_2,\dots,A_N).

For k = 1, 2, \dots, N, solve the following subproblem.

Does there exist a tuple of integers (x_1, x_2, x_3, x_4) that satisfies the following conditions? If so, find the minimum value of \sum_{i=1}^4 A_{x_i} for a tuple satisfying the conditions.

  • x_1, x_2, x_3, x_4 are all distinct.
  • x_1, x_2, x_3, x_4 are all different from k.
  • For all integers (i,j) satisfying 1 \leq i \lt j \leq 4, the x_i x_j path in T contains vertex k, and the x_i x_j path in U also contains vertex k.

You are given t test cases; solve the problem for each of them.

Constraints

  • 1 \leq t \leq 10^5
  • 5 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq u_i \lt v_i \leq N
  • 1 \leq b_i \lt c_i \leq N
  • T and U are trees.
  • The sum of N over all test cases is at most 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{case}_i means the i-th test case.

t
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_t

For each test case, the input is given in the following format:

N
A_1 A_2 \dots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
b_1 c_1
b_2 c_2
\vdots
b_{N-1} c_{N-1}

Output

Output t lines. The i-th line should contain the answer for the i-th test case.
For each test case, output the answers to the subproblems in the order k=1,2,\dots,N, separated by spaces on one line.
For each subproblem, output -1 if there does not exist a tuple of integers (x_1, x_2, x_3, x_4) satisfying the conditions, or output the minimum value of \sum_{i=1}^4 A_{x_i} for such a tuple if it exists.

Sample Input 1

2
5
20 26 1 25 213
1 5
3 5
2 5
4 5
4 5
1 5
2 5
3 5
20
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288
1 2
2 3
1 4
1 5
2 6
3 7
3 8
3 9
2 10
1 11
8 12
6 13
5 14
11 15
13 16
1 17
7 18
9 19
15 20
1 2
2 3
2 4
4 5
2 6
1 7
6 8
3 9
3 10
7 11
7 12
1 13
3 14
3 15
8 16
1 17
3 18
2 19
1 20

Sample Output 1

-1 -1 -1 -1 72
70664 616 131968 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

For the first test case, when k=1,2,3,4, there does not exist (x_1, x_2, x_3, x_4) satisfying the conditions. When k=5, (x_1,x_2,x_3,x_4) = (1,2,3,4) satisfies the conditions.