这是问题的最大化版本。版本之间的区别在于,在这个版本中,您需要找到所有公共树中可能的最大深度。此外,此版本中对 $$$n$$$ 的约束更大。只有解决了该问题的所有版本,您才能破解。
圣诞节,Tortinita 和 Arietta 各得到一棵圣诞树。巧合的是,它们的树具有相同的属性:都有 $$$n+1$$$ 顶点,并以顶点 $$$0$$$ 为根。在他们给你的圣诞贺卡中,他们每个人都会在问候后附加他们的圣诞树的 DFS 订单序列。回想一下,DFS 订单序列是由以下伪代码生成的。
dfs_order = []
def dfs(v):
dfs_order.append(v)
pick an arbitrary permutation s of children of v
for child in s:
dfs(child)
dfs(root)
设 Tortinita 树的 DFS 顺序为 $$$a_0, a_1, \ldots, a_n$$$,Arietta 树的 DFS 顺序为 $$$b_0, b_1, \ldots, b_n$$$。您观察到 $$$a_0 = b_0 = 0$$$,并且由于她们是双胞胎姐妹,您想知道她们是否可以拥有完全相同的树。你也会觉得姐妹们的圣诞树不会选择一个简单的结构。因此,您想要 找到两个序列的所有公共树中的最大可能深度$$$^{\text{*}}$$$.
$$$^{\text{*}}$$$树的深度定义为从任何节点到根的简单路径上的最大边数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le n$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \cdots, b_n$$$ ($$$1 \le b_i \le n$$$)。
保证序列 $$$a$$$ 和 $$$b$$$ 都不包含重复项。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个整数——所有常见树的最大可能深度。
示例
输入复制
421 21 221 22 153 1 5 2 44 3 2 1 552 3 4 1 53 2 1 4 5
输出复制
2131
注意
在第一个测试用例中,$$$a$$$ 和 $$$b$$$ 是相同的。考虑一个具有边 $$$(0,1)$$$ 和 $$$(1,2)$$$ 的链接树;它可以给出任一 DFS 顺序序列,其深度为 $$$2$$$。可以证明$$$2$$$是所有可能的公共树中的最大深度。
在第二个测试用例中,考虑一棵具有边 $$$(0,1)$$$ 和 $$$(0,2)$$$ 的星形树,其深度为 $$$1$$$。可以证明$$$1$$$是所有可能的公共树中的最大深度。
在第三个测试用例中,该图显示了最大深度为 $$$3$$$ 的一棵树。