← 返回题目列表

Codeforces · 1476/C

C. 最长的简单循环

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

您有 $$$n$$$ 条链,第 $$$i$$$ 条链由 $$$c_i$$$ 个顶点组成。每个链中的顶点沿着链从 $$$1$$$ 到 $$$c_i$$$ 独立编号。换句话说,第 $$$i$$$ 链是无向图,其中每个 $$$1 \le j < c_i$$$ 具有 $$$c_i$$$ 顶点和连接第 $$$j$$$ 和第 $$$(j + 1)$$$ 个顶点的 $$$(c_i - 1)$$$ 边。

现在您决定通过以下方式将链合并在一个图中:

1. 跳过第一条链;
2. 第 $$$i$$$ 链的第 $$$1$$$-st 顶点与第 $$$(i - 1)$$$ 链的第 $$$a_i$$$-th 顶点通过边连接;
3. 第 $$$i$$$ 链的最后一个(第 $$$c_i$$$)顶点通过一条边与第 $$$(i - 1)$$$ 链的第 $$$b_i$$$ 个顶点相连。

第一个测试用例的图片。虚线是在联合过程中添加的边缘

计算结果图中最长简单循环的长度。

简单循环是第一个和最后一个顶点也连接的链。如果沿着简单循环行进,则该循环的每个顶点将被访问一次。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 您拥有的链数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$2 \le c_i \le 10^9$$$) — 相应链中的顶点数。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$a_1 = -1$$$; $$$1 \le a_i \le c_{i - 1}$$$)。

每个测试用例的第四行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$b_1 = -1$$$; $$$1 \le b_i \le c_{i - 1}$$$)。

$$$a_1$$$ 和 $$$b_1$$$ 都等于 $$$-1$$$,它们不用于图形构建,只是为了索引一致性而给出。保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印最长简单循环的长度。

示例

输入 #1

3
4
3 4 3 3
-1 1 2 2
-1 2 2 3
2
5 6
-1 5
-1 1
3
3 5 2
-1 1 1
-1 3 5

输出 #1

7
11
8

注意

在第一个测试用例中,最长的简单循环如下所示:

我们不能用第一条链来增加它,因为在这种情况下它不会简单——第二条链上的顶点 $$$2$$$ 将破坏简单性。