Link Cut Tree

View as PDF

Submit solution

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

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.

Sample Input

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

Sample Output



There are no comments at the moment.