Max Mex
Contest: Codeforces Round 526 (Div. 1)
Difficulty rating: 2900
Tags: data structures, trees

Once Grisha found a tree (connected graph without cycles) with a root in node $$$1$$$.

But this tree was not just a tree. A permutation $$$p$$$ of integers from $$$0$$$ to $$$n - 1$$$ is written in nodes, a number $$$p_i$$$ is written in node $$$i$$$.

As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.

Let's define a function $$$MEX(S)$$$, where $$$S$$$ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.

Let $$$l$$$ be a simple path in this tree. So let's define indices of nodes which lie on $$$l$$$ as $$$u_1$$$, $$$u_2$$$, $$$\ldots$$$, $$$u_k$$$.

Define $$$V(l)$$$ as a set {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}.

Then queries are:

1. For two nodes $$$i$$$ and $$$j$$$, swap $$$p_i$$$ and $$$p_j$$$.
2. Find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of nodes of a tree.

The second line contains $$$n$$$ integers — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i < n$$$) — the permutation $$$p$$$, it's guaranteed that all numbers are different .

The third line contains $$$n - 1$$$ integers — $$$d_2$$$, $$$d_3$$$, $$$\ldots$$$, $$$d_n$$$ ($$$1 \leq d_i < i$$$), where $$$d_i$$$ is a direct ancestor of node $$$i$$$ in a tree.

The fourth line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain the description of queries:

At the beginning of each of next $$$q$$$ lines, there is a single integer $$$t$$$ ($$$1$$$ or $$$2$$$) — the type of a query:

1. If $$$t = 1$$$, the line also contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$) — the indices of nodes, where values of the permutation should be swapped.
2. If $$$t = 2$$$, you need to find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.

Output format:
For each type 2 query print a single integer — the answer for this query.

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

Note:
Number written in brackets is a permutation value of a node.

Example input:
6
2 5 0 3 1 4
1 1 3 3 3
3
2
1 6 3
2

Example output:
3
2

Example input:
6
5 2 1 4 3 0
1 1 1 3 3
9
2
1 5 3
2
1 6 1
2
1 4 2
2
1 1 6
2

Example output:
3
2
4
4
2

Editorial:
First let's redefine the MEX query more clearly — you need to find what is the maximum $$$a$$$, such that all nodes with permutation values up to $$$a$$$ lie on the same path.
For that you can use just a simple segment tree — in a node of a segment tree you need to store is it true that all nodes with permutation values between $$$l$$$ and $$$r$$$ lie on the same path and if so, what are the endpoints of this path. You can merge these paths using precalculated LCA and in and out times. For example you can just check all pairs of nodes from the endpoints of paths as candidates for the endpoints of a new path. So for the MEX query you need to traverse this segment tree, and for the change query you just update paths in $$$O$$$($$$log$$$ $$$n$$$) nodes of your segment tree. $$$O$$$($$$n$$$ $$$log$$$ $$$n$$$)