## Link Cut Tree

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types

In this problem, you will be required to support the following operations on a forest:

1 u v - Make node $$u$$ the parent of $$v$$ if $$v$$ is a root, and $$u$$ is not in the subtree of $$v$$.

2 u v - Delete the edge between nodes $$u$$ and $$v$$ if it exists.

3 u v - Print the highest common ancestor of nodes $$u$$ and $$v$$. If no such node exists, print -1.

There will be $$Q$$ operations of this form.

However, at most two out of the three operations will appear in any given test case.

#### Input Specification

The first line will contain one integer $$N$$ $$({1 \le N \le 10^5})$$.

The next lines will contain $$N$$ integers $$p_i$$ $$({0 \le p_i \le N})$$, the parent of node $$i$$.

Nodes with parent $$0$$ are roots.

The next line will contain one integer $$Q$$ $$({1 \le Q \le 10^5})$$.

The next $$Q$$ lines will contain one query described above.

#### Output Specification

The answers to the queries, each on one line in the order of the queries.

3
0 0 1
5
3 1 1
3 1 2
3 1 3
1 1 2
3 1 2

1
-1
1
1

## Comments

There are no comments at the moment.