P4271 [USACO18FEB] New Barns P

You need to maintain a forest that initially has no nodes. Support two types of operations: - `B p` builds a new node and connects it to node $p$. If $p = -1$, it is not connected to any other node. - `Q k` asks, within the connected component containing node $k$, for the distance to the farthest node from it. The distance is defined as the number of edges on the path between two nodes.

The first line contains a positive integer $q$, the number of operations. The next $q$ lines each describe one operation.

For each query operation, output one integer per line representing the answer.

Constraints: For $100\%$ of the testdata, $1 \le q \le 10^5$. The operations are guaranteed to be valid. The example input corresponds to this network of barns: ``` (1) \ (2)---(4) / (3) ``` In query 1, we build barn number 1. In query 2, we ask for the distance of 1 to the farthest connected barn. Since barn 1 is connected to no other barns, the answer is 0. In query 3, we build barn number 2 and connect it to barn 1. In query 4, we build barn number 3 and connect it to barn 2. In query 5, we ask for the distance of 3 to the farthest connected barn. In this case, the farthest is barn 1, which is 2 units away. In query 6, we build barn number 4 and connect it to barn 2. In query 7, we ask for the distance of 2 to the farthest connected barn. All three barns 1, 3, 4 are the same distance away, which is 1, so this is our answer. Problem credits: Anson Hu. Translated by ChatGPT 5