Trees of Tranquillity
Contest: Codeforces Round 722 (Div. 1)
Difficulty rating: 2300
Tags: data structures, dfs and similar, greedy, trees

Soroush and Keshi each have a labeled and rooted tree on $$$n$$$ vertices. Both of their trees are rooted from vertex $$$1$$$.

Soroush and Keshi used to be at war. After endless decades of fighting, they finally became allies to prepare a Codeforces round. To celebrate this fortunate event, they decided to make a memorial graph on $$$n$$$ vertices.

They add an edge between vertices $$$u$$$ and $$$v$$$ in the memorial graph if both of the following conditions hold:

- One of $$$u$$$ or $$$v$$$ is the ancestor of the other in Soroush's tree.
- Neither of $$$u$$$ or $$$v$$$ is the ancestor of the other in Keshi's tree.

Here vertex $$$u$$$ is considered ancestor of vertex $$$v$$$, if $$$u$$$ lies on the path from $$$1$$$ (the root) to the $$$v$$$.

Popping out of nowhere, Mashtali tried to find the maximum clique in the memorial graph for no reason. He failed because the graph was too big.

Help Mashtali by finding the size of the maximum clique in the memorial graph.

As a reminder, clique is a subset of vertices of the graph, each two of which are connected by an edge.

Input format:
The first line contains an integer $$$t$$$ $$$(1\le t\le 3 \cdot 10^5)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ $$$(2\le n\le 3 \cdot 10^5)$$$.

The second line of each test case contains $$$n-1$$$ integers $$$a_2, \ldots, a_n$$$ $$$(1 \le a_i < i)$$$, $$$a_i$$$ being the parent of the vertex $$$i$$$ in Soroush's tree.

The third line of each test case contains $$$n-1$$$ integers $$$b_2, \ldots, b_n$$$ $$$(1 \le b_i < i)$$$, $$$b_i$$$ being the parent of the vertex $$$i$$$ in Keshi's tree.

It is guaranteed that the given graphs are trees.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case print a single integer — the size of the maximum clique in the memorial graph.

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

Note:
In the first and third test cases, you can pick any vertex.

In the second test case, one of the maximum cliques is $$$\{2, 3, 4, 5\}$$$.

In the fourth test case, one of the maximum cliques is $$$\{3, 4, 6\}$$$.

Example input:
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

Example output:
1
4
1
3

Editorial:
Let's start with some observations.
Take any clique $$$C$$$ in the memorial graph.
Notice that the vertices of $$$C$$$ are a subset of a path from root to some leaf in Soroush's tree. So it's sufficient to solve the task for every leaf in Soroush's tree, specifically we should consider subsets of the paths starting from the root and ending in a leaf in Soroush's tree.
Assume you have a data structure that supports the following operations:
1. Insert a vertex.
2. Erase a vertex.
3. Among the vertices inside it, find the biggest set of vertices $$$S$$$ such that none of them is the ancestor of the other in Keshi's tree.
To solve the task, start doing DFS from the root of Soroush's tree. Every time you visit a new vertex $$$v$$$, add $$$v$$$ using the $$$1$$$-st operation. Every time you finish doing DFS in a vertex $$$v$$$, erase $$$v$$$ using the $$$2$$$-nd operation.
It's easy to see that the vertices in the data structure always form a path from root to some vertex $$$v$$$ in Soroush's tree.
The answer to the task is the maximum size of $$$S$$$ in the $$$3$$$-rd operation for every leaf $$$u$$$ of Soroush's tree, when adding $$$u$$$ has been the last operation in the data structure; In other words $$$ans = max(ans , x)$$$ where $$$x$$$ is the size of $$$S$$$ in the $$$3$$$-rd operation whenever you reach a leaf while doing DFS in Soroush's tree.
When adding a vertex $$$v$$$ to the data structure, if no vertex $$$u \in S$$$ existed such that $$$u$$$ was in $$$v$$$'s subtree in Keshi's tree, consider the following cases:
• If no ancestor of $$$v$$$ was in $$$S$$$, greedily add $$$v$$$ to $$$S$$$.
• Otherwise, let that ancestor be $$$w$$$, erase $$$w$$$ from $$$S$$$ and add $$$v$$$ instead.
On the other hand, if such a vertex $$$u$$$ already existed in $$$S$$$, we won't add $$$v$$$ to $$$S$$$ based on the greedy solution mentioned above.
Whatever notation used from here onwards refers to Keshi's tree unless stated.
Do a DFS on the tree and find the starting time/finishing time for each vertex.
It's widely known that vertex $$$v$$$ is an ancestor of vertex $$$u \iff$$$ $$$st_v \le st_u$$$ and $$$ft_v \ge ft_u$$$.
Observation: for any pair of vertices $$$u$$$ and $$$v$$$, segments $$$[st_u , ft_u]$$$ and $$$[st_v , ft_v]$$$ either don't share an element or one of them lies completely inside the other.
To construct the aforementioned data structure:
Let the set $$$S$$$ be a maximal set of the vertices that form a clique in the memorial graph. For each vertex $$$v$$$ we store a pair $$$\{st_v , v\}$$$ in $$$S$$$.
Now to check whether any vertex $$$u$$$ in the subtree of vertex $$$v$$$ exists in $$$S$$$: Let $$$p$$$ be the first pair in $$$S$$$ such that the first element in $$$p \ge st_v$$$. If $$$p$$$'s second element's finishing time is less than $$$ft_v$$$ then $$$p$$$'s second element is in $$$v$$$'s subtree, otherwise it's not.
Now to check whether any ancestor of $$$v$$$ is in $$$S$$$ or not: Let $$$p$$$ be the first pair in $$$S$$$ such that $$$p$$$'s first element is less than $$$st_v$$$, it can be proved that if an ancestor $$$u$$$ of $$$v$$$ exists in $$$S$$$, then $$$p = \{st_u , u\}$$$, thus we can check if $$$v$$$ is in the subtree of $$$p$$$'s second element by the aforementioned observation.
Doing the erase operation is also possible by keeping a history of the deleted elements from the set $$$S$$$.
complexity: $$$\mathcal{O}(n \log n)$$$