Tree#4325
Consider a rooted tree that initially consists of only a single root. The children of each vertex are ordered from left to right. You can perform the following operations on the tree:
Add a leaf to the tree.
Remove a leaf from the tree.
Determine the number of vertices on the path between two leaves.
Determine the number of vertices "under the path" between two leaves.
The vertices "under the path" between leaves and are defined as follows. Consider the path u = w_0 - w_1 - \ldots - w_k = v between them. Identify the vertex w_c where both edges of the path lead to its children. The left edge moves towards vertex , and the right edge moves towards vertex . The vertices considered "under the path" include:
All children of w_c that lie between w_{c-1} and w_{c+1}, along with all vertices in their subtrees.
For i = 1, 2, \ldots, c-1, all children of w_i that are to the right of child w_{i-1}, along with all vertices in their subtrees.
For i = c+1, c+2, \ldots, k-1, all children of w_i that are to the left of child w_{i+1}, along with all vertices in their subtrees.
Write a program that processes a sequence of queries to modify the tree by adding and removing vertices, and calculates the answers to queries about the number of vertices on the path and "under the path".
The first line of the input contains a single integer — the number of queries (0 \leq n \leq 300\,000). Each of the following lines contains one query. The possible types of queries are:
l x — add a new leaf as the leftmost child of vertex .
r x — add a new leaf as the rightmost child of vertex .
a x y — add a new leaf as a child of vertex , positioned immediately to the right of vertex ; all children of that were previously to the right of will be to the right of the new vertex after addition; it is guaranteed that is a child of .
d x — delete vertex . It is guaranteed that at this moment, vertex is not deleted and is a leaf.
p x y — find the number of vertices on the path between and , including these vertices themselves; it is guaranteed that and are leaves.
q x y — find the number of vertices "under the path" between and , including these vertices themselves; it is guaranteed that and are leaves.
Vertices are numbered starting from one in the order they are added through the queries. The root of the tree is numbered and is never considered a leaf.
For each query of type p or q, output the answer on a separate line as you process the queries in order.
Example 1