CF2150C.Limited Edition Shop

cYsmix - House With Legs

⠀

有一家商店，共有 $n$ 件物品，编号为 $1$ 到 $n$，每种物品都只有一件。你认为每件物品的价值分别是 $v_1, v_2, \ldots, v_n$（其中价值可以为负数）。

Alice 和 Bob 各自有自己喜欢的物品顺序（分别用 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$ 表示）。具体来说，Alice 最喜欢的物品是 $a_1$，其次是 $a_2$，依此类推；而 Bob 最喜欢的物品是 $b_1$，其次是 $b_2$，依此类推。

接下来共会有 $n$ 次操作，每次 Alice 或 Bob 中的一人去商店按自己最优先的顺序买下还未被购买的那件物品。最终，Alice 和 Bob 都会各自得到一些物品。

现在商店里的物品已经全部售罄，你想知道 Alice 的偏好是否与你相似。在 Alice 可能买到的所有物品集合中，按你的价值观，Alice 获得的物品总价值的最大值是多少？

本题包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。每个测试用例的描述如下：

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示物品数量。

第二行包含 $n$ 个整数 $v_1, v_2, \ldots, v_n$（$-10^9 \le v_i \le 10^9$），表示你认为各物品的价值。

第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示 Alice 的物品偏好顺序。$a_i$ 两两不同。

第四行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le n$），表示 Bob 的物品偏好顺序。$b_i$ 两两不同。

保证所有测试用例中的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示对你来说 Alice 能够获得的物品总价值的最大值。

在第一个测试用例中，Alice 可能获得的物品集合有 $[]$（空集）、$[1]$、$[3]$、$[3, 1]$、$[3, 1, 2]$（物品按购买时间排序）。例如，若 Alice 只买到 $[1]$，则两人进店顺序如下：

• Bob 进入并买下物品 $2$；
• Bob 进入并买下物品 $3$（因物品 $2$ 已售罄）；
• Alice 进入并买下物品 $1$（因物品 $3$ 已售罄）。

此时 Alice 能获得的最大价值集合是 $[3, 1]$，总价值为 $v_3 + v_1 = 2$。

在第二个测试用例中，Alice 和 Bob 的偏好顺序与第一个用例相同，但此时最大总价值为 $[3, 1, 2]$，即 $5$。

由 ChatGPT 5 翻译