← 返回题目列表

Codeforces · 1528/C

C. 宁静之树

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

Soroush 和 Keshi 在 $$$n$$$ 顶点上各有一棵有标签且有根的树。它们的两棵树都以顶点 $$$1$$$ 为根。

索鲁什和克什曾经处于战争状态。经过数十年无休止的战斗,他们终于成为盟友,准备进行 Codeforces 回合。为了庆祝这一幸运事件,他们决定在 $$$n$$$ 个顶点上制作一个纪念图。

如果满足以下两个条件,它们会在纪念图中的顶点 $$$u$$$ 和 $$$v$$$ 之间添加一条边:

- $$$u$$$ 或 $$$v$$$ 之一是 Soroush 树中另一个的祖先。
- $$$u$$$ 或 $$$v$$$ 都不是 Keshi 树中另一个的祖先。

这里,如果 $$$u$$$ 位于从 $$$1$$$(根)到 $$$v$$$ 的路径上,则顶点 $$$u$$$ 被视为顶点 $$$v$$$ 的祖先。

Mashtali 突然冒出来,无缘无故地试图在纪念图中找到最大的派系。他失败了,因为图表太大了。

通过找到纪念图中最大派系的大小来帮助 Mashtali。

提醒一下,团是图的顶点的子集,每两个顶点由一条边连接。

输入

第一行包含一个整数 $$$t$$$ $$$(1\le t\le 3 \cdot 10^5)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2\le n\le 3 \cdot 10^5)$$$。

每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$a_2, \ldots, a_n$$$ $$$(1 \le a_i < i)$$$,$$$a_i$$$ 是 Soroush 树中顶点 $$$i$$$ 的父节点。

每个测试用例的第三行包含 $$$n-1$$$ 整数 $$$b_2, \ldots, b_n$$$ $$$(1 \le b_i < i)$$$,$$$b_i$$$ 是 Keshi 树中顶点 $$$i$$$ 的父节点。

保证给定的图是树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数——纪念图中最大团的大小。

示例

输入 #1

4
4
1 2 3
1 2 3
5
1 2 3 4
1 1 1 1
6
1 1 1 1 2
1 2 1 2 2
7
1 1 3 4 4 5
1 2 1 4 2 5

输出 #1

1
4
1
3

注意

在第一个和第三个测试用例中,您可以选择任何顶点。

在第二个测试用例中,最大派系之一是 $$$\{2, 3, 4, 5\}$$$。

在第四个测试用例中,最大派系之一是 $$$\{3, 4, 6\}$$$。