在您的社交活动中,有 $$$n$$$ 交易等待发生。
每笔交易恰好需要两个人,并且每个人都在等待一笔交易。因此总共有 $$$2n$$$ 人,每个交易 ID $$$1 \ldots n$$$ 正好出现在两个人的徽章上。
出于公司原因,组织者将每个人放置在具有 $$$2n$$$ 个顶点的树中的唯一顶点上。 Vertex $$$v$$$ 接待了一个带有徽章 $$$a_v$$$ 的人。
如果在事件开始时,带有徽章 $$$i$$$ 的两个人位于相邻顶点,则交易 $$$i$$$ 被密封。每笔达成的交易都会为您带来 $$$w_i$$$ 收入。
活动开始前,您可以重新洗牌一次:
- 选择任何(可能为空)边集,以便没有两个选定的边共享顶点(即,边形成匹配)。
- 对于每个选定的边 $$$(u, v)$$$,交换顶点 $$$u$$$ 和 $$$v$$$ 处的人员。
重新洗牌后,您可以从本次活动中获得的最高收益是多少?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。
下一行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_i \leq 10^5$$$),其中 $$$w_i$$$ 表示交易 $$$i$$$ 的利润。
下一行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$。保证每个值 $$$1, 2, \ldots, n$$$ 在 $$$a$$$ 中恰好出现两次。
接下来的 $$$2n-1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v, \leq 2n, u \neq v$$$) — 表示一条边连接节点 $$$u$$$ 和 $$$v$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数——重新洗牌后的最大总收入。
示例
输入复制
3210 31 2 2 11 22 33 438 7 13 1 2 3 1 21 21 31 41 51 634 9 71 2 3 1 2 31 22 33 44 55 6
输出复制
10811
注意
测试 1。 交换边 $$$(1,2)$$$ 和 $$$(3,4)$$$ (它们不共享顶点)。然后,两个 1 在边 $$$(2,3)$$$ 上相邻,获得 $$$w_1=10$$$,这比保持现有的 2-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。