P4271 [USACO18FEB] New Barns P

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

无

无

【数据范围】 对于 $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