P14456 [ICPC 2025 Xi'an R] January's Color

给定一棵有根树，共有 $n$ 个顶点，根节点为顶点 $1$。保证树中不存在恰好有一个子节点的顶点。换句话说，每个顶点要么是叶子节点，要么至少有 **两个** 子节点。你拥有这棵树中的一部分顶点。 你手中可能已经拥有一些顶点。你可以通过以下两种方式获得新的顶点： - 直接从银行购买一个顶点 $i$，需要花费 $c_i$ 的费用； - 从你手中选择 **两个不同的**、具有相同父节点的顶点，将它们弃置，并免费获得它们的父节点。 现在，你有 $m$ 个查询。对于每个查询，你一开始手中仅有一个顶点 $x$，目标是最后只剩下一个顶点 $y$，且没有其他顶点剩余。请你计算达到这一目标所需的最小额外花费；如果无法做到，则输出无解。

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。对于每个测试用例： - 第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 3 \cdot 10^5$，$1 \leq m \leq 3 \cdot 10^5$），分别表示树的顶点数和查询数。 - 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^9$），表示从银行购买每个顶点的费用。 - 接下来的 $n - 1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$，$u \neq v$），表示树中的一条边。 - 接下来的 $m$ 行中，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$，$x \neq y$），表示一个查询。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $3 \cdot 10^5$。

对于每个查询，输出一个整数，表示该查询所需的最小额外花费。如果无法最终只剩下顶点 $y$，输出 $-1$。

在第一个测试用例的第一个查询中，你最初拥有顶点 $3$，目标是获得顶点 $1$。最便宜的方案是直接从银行购买顶点 $2$，花费 $c_2 = 2$。然后将顶点 $2$ 和 $3$ 弃置，免费获得它们的公共父节点顶点 $1$。可以证明这是最小花费的方案。 在第二个测试用例的第一个查询中，你同样从顶点 $3$ 开始，希望获得顶点 $1$。不同的是，这次不购买顶点 $2$，而是购买顶点 $4$ 和 $5$，花费 $c_4 + c_5 = 2$。然后将顶点 $4$ 和 $5$ 弃置，免费获得它们的父节点顶点 $2$。接着将顶点 $2$ 和 $3$ 弃置，免费获得它们的父节点顶点 $1$。可以证明这是最小花费的方案。 请注意，你不能再购买另一个顶点 $3$ 并将其与原先的顶点 $3$ 一起弃置来获得顶点 $1$，因为这两个顶点 $3$ 不满足“两个不同顶点”的要求。 翻译由 ChatGPT-5 完成