CF1476C.Longest Simple Cycle

You have $n$ chains, the $i$-th chain consists of $c_i$ vertices. Vertices in each chain are numbered independently from $1$ to $c_i$ along the chain. In other words, the $i$-th chain is the undirected graph with $c_i$ vertices and $(c_i - 1)$ edges connecting the $j$-th and the $(j + 1)$-th vertices for each $1 \le j \lt c_i$.

Now you decided to unite chains in one graph in the following way:

1. the first chain is skipped;
2. the $1$-st vertex of the $i$-th chain is connected by an edge with the $a_i$-th vertex of the $(i - 1)$-th chain;
3. the last ($c_i$-th) vertex of the $i$-th chain is connected by an edge with the $b_i$-th vertex of the $(i - 1)$-th chain.

Picture of the first test case. Dotted lines are the edges added during uniting process

Calculate the length of the longest simple cycle in the resulting graph.

A simple cycle is a chain where the first and last vertices are connected as well. If you travel along the simple cycle, each vertex of this cycle will be visited exactly once.

你有 $n$ 条链，其中第 $i$ 条链包含 $c_i$ 个顶点。每条链内的顶点独立地沿链从 $1$ 编号至 $c_i$。换言之，第 $i$ 条链是一个无向图，包含 $c_i$ 个顶点和 $(c_i - 1)$ 条边，对每个满足 $1 \le j < c_i$ 的 $j$，该图中存在一条连接第 $j$ 个顶点与第 $(j + 1)$ 个顶点的边。

现在你决定按如下方式将这些链合并为一个图：

1. 跳过第一条链；
2. 将第 $i$ 条链的第 $1$ 个顶点与第 $(i - 1)$ 条链的第 $a_i$ 个顶点用一条边相连；
3. 将第 $i$ 条链的最后一个（即第 $c_i$ 个）顶点与第 $(i - 1)$ 条链的第 $b_i$ 个顶点用一条边相连。

第一个测试用例示意图。虚线表示在合并过程中添加的边。

请计算所得图中最长简单环的长度。

简单环是指首尾顶点也相连的一条路径；若沿该简单环遍历，环上的每个顶点恰好被访问一次。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($2 \le n \le 10^5$) — the number of chains you have.

The second line of each test case contains $n$ integers $c_1, c_2, \dots, c_n$ ($2 \le c_i \le 10^9$) — the number of vertices in the corresponding chains.

The third line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_1 = -1$; $1 \le a_i \le c_{i - 1}$).

The fourth line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($b_1 = -1$; $1 \le b_i \le c_{i - 1}$).

Both $a_1$ and $b_1$ are equal to $-1$, they aren't used in graph building and given just for index consistency. It's guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, print the length of the longest simple cycle.

对于每个测试用例，输出最长简单环的长度。

In the first test case, the longest simple cycle is shown below:

We can't increase it with the first chain, since in such case it won't be simple — the vertex $2$ on the second chain will break simplicity.

在第一个测试用例中，最长的简单环如下所示：

我们无法通过第一条链来延长该环，因为此时它将不再是一个简单环——第二条链上的顶点 $2$ 将破坏环的简单性。