题目描述

有 $Q$ 次操作，两种类型：

1. 建造操作 B p：新建一个牛棚，如果 $p \neq -1$，则与现有牛棚 $p$ 连一条双向边。
2. 查询操作 Q k：查询从牛棚 $k$ 出发到它能到达的最远牛棚的距离。

保证图始终是森林（树或几棵不相连的树），动态加点和加边，在线查询。

---

核心性质

在树中有一个重要性质：

对于任意节点 $u$，距离它最远的点一定是树的某一条直径的端点之一。

因此，如果我们知道一棵树的直径的两个端点 $(a, b)$，那么对于树中任意点 $u$，

$$\text{maxDistance}(u) = \max(\text{dist}(u, a), \text{dist}(u, b)) $$

其中 $\text{dist}(u, v)$ 是树上两点间的距离。

---

思路设计

我们需要支持：

1. 动态加边：每次加入一个点（可能连接一个旧点）。
2. 维护直径：每个连通块（树）的直径信息。
3. 查询距离：快速查询任意两点距离。

---

1. 数据结构

• 并查集：维护连通块，每个集合的根节点记录该树的直径端点 $(end1, end2)$ 和直径长度 $len$。
• LCA 求距离：由于树是动态生长的，可以维护每个节点的深度 $depth[x]$ 和父节点 $parent[x][0]$（倍增数组），支持 $O(\log n)$ 求两点距离。

---

2. 合并时的直径更新

当新点 $x$ 与旧点 $p$ 相连（或两棵树通过新边合并）时，新直径的候选只有三种可能：

1. 原树 $T$ 的直径 $(a,b)$
2. 新点 $x$ 到 $a$ 的路径
3. 新点 $x$ 到 $b$ 的路径

因为 $x$ 是叶子节点，所以新直径必定是：

• 原直径
• $x$ 到 $a$ 的路径
• $x$ 到 $b$ 的路径

中最长的一条。

更一般地（如果合并两棵旧树），新直径候选来自：

• 树 $T_1$ 的直径
• 树 $T_2$ 的直径
• $T_1$ 的直径端点与 $T_2$ 的直径端点之间的路径

---

3. 算法步骤

• 初始化：第一个牛棚 $1$，直径端点 $(1,1)$，长度 $0$。
• 对于 B p：
  • 新建节点 $x$，若 $p \neq -1$，连接 $x$ 与 $p$。
  • 更新 $x$ 的深度和父节点信息。
  • 找到 $p$ 所在树的直径端点 $a,b$。
  • 计算 $d_1 = \text{dist}(x,a)$，$d_2 = \text{dist}(x,b)$。
  • 新直径长度 $= \max(len, d_1, d_2)$，对应端点更新。
• 对于 Q k：
  • 找到 $k$ 所在树的直径端点 $a,b$。
  • 输出 $\max(\text{dist}(k,a), \text{dist}(k,b))$。

---

距离计算

使用倍增 LCA：

• 预处理 $parent[u][k]$ 表示 $u$ 的 $2^k$ 级祖先。
• $\text{dist}(u,v) = depth[u] + depth[v] - 2 \times depth[\text{LCA}(u,v)]$。

每次加边时更新新点的深度和父节点信息。

---

复杂度分析

• 每次加边/查询：$O(\log n)$（LCA 查询）
• 总复杂度：$O(Q \log Q)$，满足 $Q \le 10^5$。

---

样例模拟

输入：

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

过程：

1. B -1：建节点 $1$，直径=$(1,1)$，长度=0
2. Q 1：maxDistance(1) = 0
3. B 1：建节点 $2$，连 $1$。
   原直径=$(1,1)$，长度=0
   计算 dist(2,1)=1，新直径=$(1,2)$，长度=1
4. B 2：建节点 $3$，连 $2$。
   原直径=$(1,2)$，长度=1
   dist(3,1)=2，dist(3,2)=1
   新直径=$(1,3)$，长度=2
5. Q 3：直径端点 $1,3$，dist(3,1)=2，dist(3,3)=0，输出 2
6. B 2：建节点 $4$，连 $2$。
   原直径=$(1,3)$，长度=2
   dist(4,1)=2，dist(4,3)=2
   新直径不变，长度=2
7. Q 2：直径端点 $1,3$，dist(2,1)=1，dist(2,3)=1，输出 1

输出：

0
2
1

与样例一致。

总结

本题的关键点：

1. 利用树的直径性质：任意点的最远点一定是直径端点。
2. 动态维护直径：合并时新直径候选来自原有直径端点组合。
3. LCA 求距离：使用倍增法支持快速查询。
4. 并查集维护连通块：同时记录每块的直径信息。

这样就能在 $O(Q \log Q)$ 时间内解决动态加边和查询问题。

核心性质 在树中，任意点 $u$ 的最远点一定是树的某条直径的端点。

思路 并查集维护连通块。

对每个连通块，记录其直径的两个端点 $(a, b)$ 和直径长度 $len$。

加边（新点 $x$ 连到旧点 $p$）时：

计算 $x$ 到原直径两端点 $a, b$ 的距离 $d_1, d_2$。

新直径的候选为：

原直径长度 $len$

$d_1$（新端点 $x, a$）

$d_2$（新端点 $x, b$）

取最大值更新直径信息。

查询 $Q\ k$：

计算 $k$ 到当前块直径两端点的距离，输出较大值。

复杂度 用 BFS 求距离：每次操作 $O(n)$ 最坏，可能被卡。

优化：用倍增 LCA $O(\log n)$ 求两点距离。