← 返回题目列表

Codeforces · 1958/I

I. 平等树

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

给你两棵有根树,每棵树由 $$$n$$$ 个顶点组成。树中的顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。

您可以执行以下操作:选择树以及其中的顶点$$$v$$$(树的根除外);将 $$$v$$$ 的子节点连接到 $$$v$$$ 的父节点,并从树中删除 $$$v$$$。

如果满足以下两个条件,则可以说两棵树相等:

- 两棵树中剩余顶点的集合相同;
- 对于每个未删除的顶点 $$$v$$$,其在第一棵树中的父节点与其在第二棵树中的父节点相同。

你的任务是计算上述操作的最少次数以使树相等。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 40$$$) — 树中的顶点数。

第二行包含 $$$n-1$$$ 整数 $$$a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是第一棵树中第 $$$i$$$ 个顶点的父节点。顶点 $$$1$$$ 是根。

第三行包含 $$$n-1$$$ 整数 $$$b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le n$$$),其中 $$$b_i$$$ 是第二棵树中第 $$$i$$$ 个顶点的父顶点。顶点 $$$1$$$ 是根。

输出

打印一个整数——为了使树相等而进行上述操作的最少次数。

示例

输入 #1

5
1 5 5 1
1 4 1 2

输出 #1

4

输入 #2

2
1
1

输出 #2

0

输入 #3

10
4 7 10 6 2 9 7 1 1
1 2 10 3 4 6 6 5 5

输出 #3

10