这道题本质上是在一个特殊结构的无向图中,求一个最长简单环的长度。
图的结构很规整:
背景:多多最近准备做一次 city walk,利用城市中的道路以及道路上的景点,规划一次 city walk 路径,目前了解到的道路和景点信息如下;
1、城市中有 n 条平行的主干道 (n≥2),第 i 条主干道上有 ci 个景点 (ci≥2)
2、对于第 j+1 条主干道,它的第一个景点和最后一个景点 cj+1 有如下特征;
2.1、第 j+1 条主干道上第一个景点,有一条小路连接着第 j 条主干道上的 aj 景点 (1≤aj≤cj)
2.2、第 j+1 条主干道上最后一个景点 cj+1,有一条小路连接着第 j 条主干道上的 bj 景点 (1≤bj≤cj)
2.3、aj 和 bj 大小无约束,且两者可能相等
一个例子如下,其中每条竖线代表一个主干道,竖线上每个点代表一个景点,虚线代表连着两个主干道的一条小路,多 多 city walk 的路径要求如下:
1、可以从任意主干道上的任意景点出发,可以走主干道,也可以走小路,要求每个景点只能走一次,不能重复,最后回到出发点
2、路线可以选择主干道上任意景点,无需覆盖主干道上所有景点
提问:如果主干道或者小路上连接两个景点的长度为 1 ,那请问多多应该如何规划 city walk 路径,使得经过的景点最多?

第一行是一个整数 t(1≤t≤103),表明测试用例数
每个测试用例第一行是一个整数 n(2≤n≤104),表明主干道的数量
每个测试用例第二行是 n 个整数 c1,c2,...,cn(2≤ci≤105),表明每个主干道上景点的数量
每个测试用例第三行是 n−1 个整数 a1,a2,...,an(1≤ai≤ci),其中 ai 表示第 i 条主干道上和 i+1 条主干道的第一个景点 1 连接的景点编号
每个测试用例第四行是 n−1 个整数 b1,b2,...,bn(1≤bi≤ci),其中 bi 表示第 i 条主干道上和 i+1 条主干道的最后一个景点 ci+1 连接的景点编号
对于每个测试用例,输出最长 city walk 路径的长度
输入
3
4
3 4 3 3
1 2 2
2 2 3
2
5 6
5
1
3
3 5 2
1 1
3 5
输出
7
11
8
说明
第一个测试用例的最长路径如下,我们无法把路径拓展到主干道 1,否则主干道 2 上的节点 2 会被访问 2 次
