解题思路

这道题本质上是在一个特殊结构的无向图中，求一个最长简单环的长度。

图的结构很规整：

P4697.第4题-多多的city walk路径

1000ms

Difficulty: 6

所属公司 : 拼多多

算法与标签>动态规划

背景：多多最近准备做一次 $city$ $walk$ ，利用城市中的道路以及道路上的景点，规划一次 $city$ $walk$ 路径，目前了解到的道路和景点信息如下；

1、城市中有 $n$ 条平行的主干道 ( $n≥2$ )，第 $i$ 条主干道上有 $c_i$ 个景点 ( $c_i≥2$ )

2、对于第 $j+1$ 条主干道，它的第一个景点和最后一个景点 $c_{j+1}$ 有如下特征；

2.1、第 $j+1$ 条主干道上第一个景点，有一条小路连接着第 $j$ 条主干道上的 $a_j$ 景点 ( $1≤a_j≤c_j$ )

2.2、第 $j+1$ 条主干道上最后一个景点 $c_{j+1}$ ，有一条小路连接着第 $j$ 条主干道上的 $b_j$ 景点 ( $1≤b_j≤c_j$ )

2.3、 $a_j$ 和 $b_j$ 大小无约束，且两者可能相等

一个例子如下，其中每条竖线代表一个主干道，竖线上每个点代表一个景点，虚线代表连着两个主干道的一条小路，多多 $city$ $walk$ 的路径要求如下：

1、可以从任意主干道上的任意景点出发，可以走主干道，也可以走小路，要求每个景点只能走一次，不能重复，最后回到出发点

2、路线可以选择主干道上任意景点，无需覆盖主干道上所有景点

提问：如果主干道或者小路上连接两个景点的长度为 $1$ ，那请问多多应该如何规划 $city$ $walk$ 路径，使得经过的景点最多？

第一行是一个整数 $t(1≤t≤10^3)$ ，表明测试用例数

每个测试用例第一行是一个整数 $n(2≤n≤10^4)$ ，表明主干道的数量

每个测试用例第二行是 $n$ 个整数 $c_1,c_2,...,c_n(2≤c_i≤10^5)$ ，表明每个主干道上景点的数量

每个测试用例第三行是 $n-1$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤c_i)$ ，其中 $a_i$ 表示第 $i$ 条主干道上和 $i+1$ 条主干道的第一个景点 $1$ 连接的景点编号

每个测试用例第四行是 $n-1$ 个整数 $b_1,b_2,...,b_n(1≤b_i≤c_i)$ ，其中 $b_i$ 表示第 $i$ 条主干道上和 $i+1$ 条主干道的最后一个景点 $c_{i+1}$ 连接的景点编号

对于每个测试用例，输出最长 $city$ $walk$ 路径的长度

输入

输出

7
11
8

说明

第一个测试用例的最长路径如下，我们无法把路径拓展到主干道 $1$ ，否则主干道 $2$ 上的节点 $2$ 会被访问 $2$ 次

输入

预期输出（选填）