New Barns

题目描述

农夫约翰发现，如果奶牛被挤得太近，它们就容易争吵，因此他想新建一系列牛棚来把它们分散开。

每当 FJ 新建一个牛棚时，他至多会用一条双向通道把它连接到一个已有的牛棚。为了确保奶牛之间距离足够远，他有时想要确定：从某个牛棚出发，在能够到达的所有牛棚中，最远的那个与它的距离（两个牛棚之间的距离定义为从一个牛棚到另一个牛棚需要经过的通道条数）。

FJ 一共会给出 $Q$（$1 \leq Q \leq 10^5$）个询问，每个询问要么是“build”，要么是“distance”。对于 build 询问，FJ 新建一个牛棚，并将其与至多一个之前建好的牛棚相连。对于 distance 询问，FJ 询问从某个牛棚出发，沿着若干通道可到达的最远牛棚与它的距离。保证被询问的牛棚已经建好。

请帮助 FJ 回答所有这些询问。

输入格式

第一行是整数 $Q$。接下来的 $Q$ 行每行一个询问。

每个询问的格式为 "B p" 或 "Q k"，分别表示：建造一个牛棚并将其与牛棚 $p$ 相连，或询问从牛棚 $k$ 出发的最远距离（定义如题）。

如果 $p = -1$，则新牛棚不与任何其他牛棚相连。否则，$p$ 是一个已经建好的牛棚的编号。

牛棚编号从 $1$ 开始，因此第一个建好的牛棚编号为 $1$，第二个为 $2$，以此类推。

输出格式

对于每个 distance 询问输出一行。

注意：一个不与任何其他牛棚相连的牛棚，其最远距离为 $0$。

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

0_x000D_
2_x000D_
1

提示

样例输入对应如下的牛棚网络： (1) \
(2)---(4) / (3) 在第 1 个询问中，我们建造编号为 1 的牛棚。在第 2 个询问中，我们询问从 1 出发到最远的已连接牛棚的距离。由于牛棚 1 不与任何其他牛棚相连，答案为 0。在第 3 个询问中，我们建造编号为 2 的牛棚并将其连接到牛棚 1。在第 4 个询问中，我们建造编号为 3 的牛棚并将其连接到牛棚 2。在第 5 个询问中，我们询问从 3 出发到最远的已连接牛棚的距离。在这种情况下，最远的是牛棚 1，距离为 2。在第 6 个询问中，我们建造编号为 4 的牛棚并将其连接到牛棚 2。在第 7 个询问中，我们询问从 2 出发到最远的已连接牛棚的距离。牛棚 1、3、4 到牛棚 2 的距离都相同，都是 1，因此答案为 1。 题目鸣谢：Anson Hu

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum