Common Ancestor - 3#3300
A suspended tree is a directed graph that contains no cycles, where each vertex, except for one designated as the root, has exactly one incoming edge. The root of the tree has no incoming edges. In this context, the parent of a vertex is the vertex from which an edge leads to it.
You are given a collection of suspended trees and need to execute the following operations:
0 u v - For two specified vertices and , determine if they belong to the same tree. If they do, output their lowest common ancestor (LCA); if not, output .
1 u v - Given the root of one tree and any vertex from another tree, add an edge . This operation merges the two trees into a single tree.
These operations must be performed online, meaning each query is revealed only after the previous one has been processed.
The first line of the input contains the integer , representing the total number of vertices across all trees (1 \leq n \leq 50000). The second line provides integers, each indicating the parent of the corresponding vertex in the initial setup, or if the vertex is a root. The next line contains the integer , the number of queries (1 \leq k \leq 100000). Each of the following lines contains three integers: the query type ( for finding the LCA or for adding an edge) and two integers and . The vertices involved in the query are determined using the formulas: u = (x - 1 + ans) \bmod n + 1 and v = (y - 1 + ans) \bmod n + 1, where is the result of the last query of type .
For each query of type , output the result on a separate line.
Esempio 1
Esempio 2