分数: 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) 满足条件。