CF2217H Closer

在你的社交活动中，有 $n$ 个交易等待达成。 每个交易恰好需要两个人，并且每个人只等待一个交易。所以总共有 $2n$ 个人，每个交易编号 $1 \ldots n$ 恰好出现在两个人的徽章上。 出于公司原因，组织方将每个人分别放置在一棵有 $2n$ 个顶点的树的唯一一个顶点上。顶点 $v$ 上的人佩戴徽章 $a_v$。 如果活动开始时，编号为 $i$ 的两个徽章恰好在相邻的顶点上，则交易 $i$ 完成。每完成一笔交易可获得 $w_i$ 的收益。 在活动开始前，你可以进行一次重新整理： 1. 可以选择任意（可能为空）的边的集合，使得没有两条被选中的边共享顶点（也就是说，这些边形成一个匹配）。 2. 对于每条选中的边 $(u, v)$，交换顶点 $u$ 与 $v$ 上的两个人。 请问，重新整理后你最多能获得多少收益？

每组测试数据包含多组测试用例。第一行是测试用例组数 $t$（$1 \leq t \leq 10^4$）。接下来是每组测试用例的描述。 每组测试用例第一行是一个整数 $n$（$1 \leq n \leq 10^5$）。 下一行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$0 \leq w_i \leq 10^5$），表示完成第 $i$ 个交易可获得的收益。 下一行包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$，保证每个 $1, 2, \ldots, n$ 恰好出现两次。 接下来的 $2n-1$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq 2n$, $u \neq v$），表示树中连接顶点 $u$ 和 $v$ 的一条边。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示重新整理后你最多能够获得的总收益。

样例 1：交换边 $(1,2)$ 和 $(3,4)$（它们不共享顶点）。此时，两个 $1$ 将分别位于顶点 $2$ 和 $3$，它们通过边 $(2,3)$ 相邻，获得 $w_1=10$ 的收益，这比原来两个 $2$ 相邻获得的 $3$ 更优。 样例 2：树是一颗星形。交换 $(1,2)$，把徽章 $1$ 移到中心节点，使其与另一个 $1$ 相邻，实现 $w_1=8$ 的收益。 样例 3：交换 $(1,2), (3,4), (5,6)$，一次达成两笔交易：使边 $(2,3)$ 成为 $1-1$（收益 $4$），边 $(4,5)$ 成为 $3-3$（收益 $7$），总共 $11$。 由 ChatGPT 5 翻译