Dynamic Tree Diameter Queries

You are given an initially empty forest (a set of trees). You need to support two kinds of operations:

• B p — create a new node. If p = -1, the new node will be isolated; otherwise, connect the new node to the existing node p.
• Q k — for the connected component (tree) that contains node k, find the maximum distance from node k to any other node. The distance between two nodes is defined as the number of edges on the unique simple path between them.

Note: Nodes are numbered in the order they are added (starting from 0). It is guaranteed that when an operation refers to a node (other than -1), that node has already been created.

Hint: In a tree, if the diameter (the longest distance between any two nodes) has endpoints \(u\) and \(v\), then the answer to a query on node \(k\) is \(\max(\mathrm{dist}(k,u),\;\mathrm{dist}(k,v))\). You might consider computing lowest common ancestors (LCA) dynamically to calculate distances.

All formulas are in LaTeX format; for example, the distance between two nodes \(u\) and \(v\) is given by:

[ \mathrm{dist}(u,v)=\mathrm{depth}(u)+\mathrm{depth}(v)-2\cdot\mathrm{depth}(\mathrm{LCA}(u,v)) ]

inputFormat

The first line contains the number of operations n (n lines follow).

Each of the next n lines is either:

• B p — where p is an integer. If p = -1, create an isolated node; otherwise, connect the new node to node p.
• Q k — where k is a node index for which you must answer the query.

outputFormat

For each query operation Q k, output a line containing the maximum distance from node k to any other node in its connected component.

sample

4
B -1
B 0
B 0
Q 1

2