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 翻译