AT_arc213_c.[ARC213C] Double X

给定两棵树 $T$ 和 $U$，每棵树有 $N$ 个顶点，顶点编号为 $1$ 到 $N$。树 $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 < j \leq 4$ 的 $(i, j)$，在 $T$ 上 $x_i$ 到 $x_j$ 的路径包含顶点 $k$，并且在 $U$ 上 $x_i$ 到 $x_j$ 的路径也包含顶点 $k$。

给出 $t$ 组测试数据，分别求解每组数据。

输入由标准输入读取。记 $\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$ 每个子问题的答案，答案间用空格分隔。
如果不存在满足条件的整数四元组 $(x_1, x_2, x_3, x_4)$，输出 $-1$；如果存在，输出 $\sum_{i=1}^4 A_{x_i}$ 的最小值。

样例说明 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)$ 满足所有条件。

数据范围

• $1 \leq t \leq 10^5$
• $5 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq u_i < v_i \leq N$
• $1 \leq b_i < c_i \leq N$
• $T$ 和 $U$ 均为树。
• 所有测试数据中 $N$ 的总和不超过 $10^5$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译