← 返回题目列表

AtCoder · arc213_c

C. 双 X

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

分数: 900 点

问题陈述

你有两棵树 T 和 U,每个都有 N 顶点编号自 1 to N。的 i第边缘 T 连接顶点 u_i 和 v_i。的 i第边缘 U 连接顶点 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.
  • 对于所有整数 (i,j) 满意 1 \leq i \lt j \leq 4, x_i x_j 路径 T 包含顶点 k,以及 x_i x_j 路径 U 还包含顶点 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) 满足条件,或输出最小值 \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

对于第一个测试用例,当 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) 满足条件。