题目描述

给你一棵树，初始没有节点。你需要支持两种操作：

• B p 表示新建一个节点，将它与 $p$ 节点连接；若 $p=-1$，则表示不与其它节点相连

• Q k 表示查询在 $k$ 节点所在的连通块中，距它最远的点的距离。这里距离的定义是两点间经过的边数。

输入格式

第一行一个正整数 $q$，表示操作个数。
接下来 $q$ 行，每行表示一个操作。

输出格式

对于每个询问操作，输出一行一个整数表示答案。

7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2

0
2
1

提示

【数据范围】

对于 $100$ 的数据，$1 \le q \le 10^5$。
保证操作合法。

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