← 返回题目列表

Codeforces · 2217/H

H. 更近

中文机器翻译题面 查看原题

在您的社交活动中,有 $$$n$$$ 交易等待发生。

每笔交易恰好需要两个人,并且每个人都在等待一笔交易。因此总共有 $$$2n$$$ 人,每个交易 ID $$$1 \ldots n$$$ 正好出现在两个人的徽章上。

出于公司原因,组织者将每个人放置在具有 $$$2n$$$ 个顶点的树中的唯一顶点上。 Vertex $$$v$$$ 接待了一个带有徽章 $$$a_v$$$ 的人。

如果在事件开始时,带有徽章 $$$i$$$ 的两个人位于相邻顶点,则交易 $$$i$$$ 被密封。每笔达成的交易都会为您带来 $$$w_i$$$ 收入。

活动开始前,您可以重新洗牌一次:

  1. 选择任何(可能为空)边集,以便没有两个选定的边共享顶点(即,边形成匹配)。
  2. 对于每个选定的边 $$$(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$$$。

输出

对于每个测试用例,输出一个整数——重新洗牌后的最大总收入。

示例

输入
复制

3
2
10 3
1 2 2 1
1 2
2 3
3 4
3
8 7 1
3 1 2 3 1 2
1 2
1 3
1 4
1 5
1 6
3
4 9 7
1 2 3 1 2 3
1 2
2 3
3 4
4 5
5 6

输出
复制

10
8
11

注意

测试 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。