Equal Trees
Contest: Kotlin Heroes: Episode 10
Difficulty rating: 3100
Tags: *special, graphs, meet-in-the-middle

You are given two rooted trees, consisting of $$$n$$$ vertices each. The vertices in the trees are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$.

You can perform the following operation: choose the tree and the vertex $$$v$$$ (except the root of the tree) in it; connect the child nodes of $$$v$$$ to the parent of $$$v$$$ and remove $$$v$$$ from the tree.

Let's say that two trees are equal if both of the following conditions hold:

- the sets of remaining vertices in both trees are the same;
- for every vertex $$$v$$$ which is not deleted, its parent in the first tree is the same as its parent in the second tree.

Your task is to calculate the minimum number of aforementioned operation in order to make the trees equal.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 40$$$) — the number of vertices in the trees.

The second line contains $$$n-1$$$ integers $$$a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ the parent of the $$$i$$$-th vertex in the first tree. Vertex $$$1$$$ is the root.

The third line contains $$$n-1$$$ integers $$$b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le n$$$), where $$$b_i$$$ the parent of the $$$i$$$-th vertex in the second tree. Vertex $$$1$$$ is the root.

Output format:
Print a single integer — the minimum number of aforementioned operation in order to make the trees equal.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5
1 5 5 1
1 4 1 2

Example output:
4

Example input:
2
1
1

Example output:
0

Editorial:
The constraint $$$n \le 40$$$ might imply that we are looking for a meet-in-the-middle approach. Let's try to reduce this problem to one of the problems that can be solved using meet-in-the-middle.
The first key observation that we need is that if $$$i$$$ is an ancestor of $$$j$$$, and we don't remove any of these vertices from the tree, $$$i$$$ will always be an ancestor of $$$j$$$.
Let's try to figure out when two vertices $$$i$$$ and $$$j$$$ cannot be left in the answer together. If $$$i$$$ is an ancestor of $$$j$$$ in one of the trees, but not in the other tree (same for swapping $$$i$$$ and $$$j$$$), then leaving them both in the answer means that the trees won't be equal.
The second key observation is that any set of vertices such that the "ancestor relations" between them are the same in both trees is a valid set (i. e. if we leave only vertices from these sets, both trees will be equal). This is because if we know the set of ancestors for every vertex, the structure of the rooted tree is uniquely determined (for every vertex $$$i$$$, its parent is the vertex $$$j$$$ such that it is an ancestor of $$$i$$$ and not an ancestor of any other ancestor of $$$i$$$).
So, let's construct a graph on $$$n$$$ vertices, where an edge between $$$i$$$ and $$$j$$$ means that the "ancestor relation" between $$$i$$$ and $$$j$$$ is the same in both trees. We have to find the maximum clique in this graph, and this clique will be the set of vertices we don't delete.
We can use meet-in-the-middle to find the maximum clique. However, I want to showcase a very cool technique of finding the maximum clique in $$$O(n \cdot 2^{0.5n})$$$ without using meet-in-the-middle.
Let's write a recursive brute force approach. Let the current "state" of brute force be the bitmask of vertices such that they are adjacent to every vertex we already picked. Also, let our recursive function return the maximum number of vertices from the mask we can take.
Find the first vertex in the mask (let it be $$$v$$$). There are two cases:
• either $$$v$$$ belongs to the clique; then we call the recursive function from the bitwise AND of the current mask and the mask of all vertices adjacent to $$$v$$$;
• or $$$v$$$ does not belong to the clique; then we call the recursive function from the current mask with the $$$v$$$-th bit set to $$$0$$$.
If we add memoization (save the answer for every recursive call), it works in $$$O(n \cdot 2^{0.5n})$$$! This exclamation mark is not the factorial sign. To prove it, consider the depth of recursion:
• if the depth is at least $$$\frac{n}{2}$$$, all $$$\frac{n}{2}$$$ first bits are set to $$$0$$$, so there are $$$2^{0.5n}$$$ possible values for the mask;
• otherwise, we made at most $$$\frac{n}{2}$$$ choices from two options, so there are also just $$$2^{0.5n}$$$ possible values for the mask.