[USACO18FEB]New Barns P

题目描述

给你一棵树,初始只有一个节点。你需要支持两种操作: - `B p` 表示新建一个节点,将它与 $p$ 节点连接;若 $p=-1$,则表示不与其它节点相连 - `Q k` 表示查询在 $k$ 节点所在的连通块中,距它最远的点的距离。这里距离的定义是两点间经过的边数。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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