题意理解

我们有一棵 $n$ 个结点的有根树 $T^1$（根是 $1$ 号结点）。 定义 $T^m$ 的生成规则为：

$T^1$ 已知。

$T^m$ 是在 $T^{m-1}$ 的每个叶结点下面连接一棵 $T^1$ 的根结点（即把 $T^1$ 复制一份，根接到 $T^{m-1}$ 的每个叶子上）。

要求 $T^m$ 的直径（路径上的结点数）。

---

1. 基本思路

树的直径常用两次 BFS/DFS 求法：

从任意点出发找到最远的点 $u$；

从 $u$ 出发找到最远的点 $v$，$u$ 到 $v$ 的路径就是直径。

但这里 $m$ 可能很大（$2\times 10^5$），$T^m$ 的结点数会指数级增长，不能显式建树。

我们需要找到 $T^m$ 直径的递推规律。

---

2. 符号与定义

设：

$D(T)$ 表示树 $T$ 的直径（结点数）。

$h(T)$ 表示从根到叶子的最长路径的结点数（根深度为 $1$）。

$L(T)$ 表示从根到叶子的最长路径的结点数（其实 $h(T)$ 就是这个）。

$F(T)$ 表示从根出发的最长路径的结点数（其实和 $h(T)$ 一样）。

$M(T)$ 表示树中离根最远的结点到根的距离（结点数减 $1$ 是边数，这里我们统一用结点数）。

但更关键的是： 设 $a(T)$ = 从根出发的最长路径长度（结点数）， 设 $b(T)$ = 树中任意两点之间的最长路径（即直径）。

那么 $a(T^1)$ 就是 $T^1$ 的根到最远叶子的结点数， $b(T^1)$ 就是 $T^1$ 的直径。

---

3. 递推分析

3.1 从 $T^{m-1}$ 到 $T^m$ $T^m$ 的构造：在 $T^{m-1}$ 的每个叶子下接一个 $T^1$ 的根。

那么：

$T^{m-1}$ 的叶子有 $leaf(T^{m-1})$ 个。

每个叶子下面挂一个 $T^1$，所以每个叶子所在的“位置”会多出 $a(T^1)$ 的路径（从该叶子到新子树中最远的叶子）。

3.2 新直径的可能情况

$T^m$ 的直径可能出现在：

完全在某个 $T^{m-1}$ 内部：$b(T^{m-1})$。

完全在某个新加的 $T^1$ 内（不可能比情况 1 大，因为 $b(T^1) \le b(T^{m-1})$ 当 $m\ge 2$ 时？不一定，要小心）。

经过 $T^{m-1}$ 的一部分和某个新加的 $T^1$ 的一部分： 路径形如：在 $T^{m-1}$ 中从结点 $u$ 到某个叶子 $v$，然后进入该叶子下面的 $T^1$ 到达其最深的叶子 $w$。 这条路径长度 = $[u \to v \text{ 在 } T^{m-1} \text{中的距离}] + a(T^1)$。

为了最大化这个，我们应取 $T^{m-1}$ 中离 $v$ 最远的点 $u$。 对于固定的 $v$（它是 $T^{m-1}$ 的一个叶子），离它最远的点可能是另一个叶子 $v'$，那么路径就是 $T^{m-1}$ 的直径，但这样 $v$ 和 $v'$ 都是叶子，它们之间的路径不经过新加的子树，所以不进入 $T^1$，这其实是情况 1。

我们要进入新子树，必须让路径的一端在新子树中。 所以考虑： 路径一端在某个新加的 $T^1$ 的最深叶子 $P$，另一端在另一个新加的 $T^1$ 的最深叶子 $Q$（或 $T^{m-1}$ 中的某个点）。

3.3 更清晰的分解

设：

$d_1$ = $T^{m-1}$ 的直径长度。

$H$ = $T^{m-1}$ 中从根到叶子的最大结点数（即高度，根为 1 层）。

$h_1$ = $T^1$ 中从根到叶子的最大结点数（高度）。

$T^m$ 的直径可能为：

$d_1$（完全在 $T^{m-1}$ 内部）。

路径从 $T^{m-1}$ 中某个点 $x$，走到某个叶子 $y$，然后进入该叶子的 $T^1$ 到达其最深叶子：长度 = $\mathrm{dist}_{T^{m-1}}(x, y) + h_1$。 对固定的 $y$，最大化 $\mathrm{dist}(x,y)$ 就是找 $T^{m-1}$ 中离 $y$ 最远的点，这个最大值是 $d_1$ 吗？不一定，因为 $y$ 是叶子，离它最远的点可能是另一个叶子，距离就是 $d_1$，但这样 $x$ 也是叶子，路径完全在 $T^{m-1}$ 中，不加 $h_1$。 所以我们要让 $x$ 在另一个新子树中：即路径穿过 $T^{m-1}$ 连接两个不同的新子树。

3.4 跨两个新子树的路径

考虑 $T^{m-1}$ 中两个不同的叶子 $u$ 和 $v$，它们下面各挂了一个 $T^1$。 路径：从 $u$ 下面的 $T^1$ 的最深叶子 $A$，到 $v$ 下面的 $T^1$ 的最深叶子 $B$。 长度 = $h_1 + \mathrm{dist}_{T^{m-1}}(u,v) + h_1$。

那么 $\mathrm{dist}_{T^{m-1}}(u,v)$ 最大是多少？ $u$ 和 $v$ 是叶子，它们的距离等于 $depth[u] + depth[v] - 2\times depth[\mathrm{lca}(u,v)]$。 为了最大化它，我们取 $T^{m-1}$ 中深度最大的两个叶子，且它们的 LCA 是根（即在不同分支上）。 实际上，$T^{m-1}$ 中两个叶子的最大距离就是 $d_1$ 吗？ 不一定，因为 $T^{m-1}$ 的直径端点不一定是叶子？ 不，树的直径端点一定是叶子（除非只有一个结点）。所以是的，直径端点就是两个叶子。

所以 $\max \mathrm{dist}_{T^{m-1}}(u,v) = d_1$。

因此这种情况的长度 = $d_1 + 2 h_1 - 1$？ 不对，检查： $A$ 到 $u$：$h_1 - 1$ 条边？ 我们用的是结点数。 $A$ 到 $u$ 在 $T^m$ 中的结点数 = $h_1$（因为 $u$ 是 $T^1$ 的根的父亲？ 等等，构造是：$T^{m-1}$ 的叶子 $u$ 下面接 $T^1$ 的根 $r$，所以 $u$ 到 $r$ 有一条边，$r$ 到最深叶子 $A$ 有 $h_1 - 1$ 条边，所以 $u$ 到 $A$ 有 $h_1$ 个结点？ 不对，$u$ 到 $A$：路径 $u \to r \to \dots \to A$，结点依次是 $u, r, \dots, A$，总数为 $1 + (h_1) = h_1 + 1$？ 我们算一下：

$T^1$ 的高度（结点数）是 $h_1$，即从根到最深叶子有 $h_1$ 个结点。 现在 $T^1$ 的根 $r$ 接在 $u$ 下面，所以 $u$ 到 $A$ 的结点数 = $1$ (u) + $h_1$ (从 $r$ 到 $A$) = $h_1 + 1$？ 不对，这样重复计算了 $u$ 和 $r$ 吗？ 我们明确一点：

$T^1$ 内部：根 $r$ 到最深叶子 $A$ 有 $h_1$ 个结点。 现在 $u$ 是 $T^{m-1}$ 的叶子，$u$ 与 $r$ 连边，所以 $u$ 到 $A$ 的路径：$u, r, \dots, A$，结点数 = $1 + h_1$？ 不对，因为 $r$ 到 $A$ 是 $h_1$ 个结点，其中 $r$ 是第一个，$A$ 是最后一个。所以 $u$ 到 $A$ 的结点数 = $1$ (u) + $h_1$ (r到A) = $h_1 + 1$。

同理 $v$ 到 $B$ 也是 $h_1 + 1$ 个结点。

那么 $A$ 到 $B$ 的路径：$A\to \dots \to r_u \to u \to \dots \to v \to r_v \to \dots \to B$。 结点数 = $(h_1) + [u \to v \text{ 在 } T^{m-1} \text{ 中的结点数}] + (h_1)$。 但 $u\to v$ 在 $T^{m-1}$ 中的结点数 = $\mathrm{dist}{T^{m-1}}(u,v) + 1$（边数+1）。 所以总结点数 = $h_1 + (\mathrm{dist}{T^{m-1}}(u,v) + 1) + h_1$ = $2 h_1 + \mathrm{dist}_{T^{m-1}}(u,v) + 1$。

取 $\mathrm{dist}{T^{m-1}}(u,v) = d_1 - 1$（因为 $u,v$ 是直径端点，它们之间的距离是 $d_1 - 1$ 条边？ 等等，之前混淆了：$d_1$ 是直径的结点数，边数 = $d_1 - 1$。 那么 $\mathrm{dist}{T^{m-1}}(u,v)$ 的结点数 = $d_1$（因为路径上的结点数就是 $d_1$）。 所以 $A$ 到 $B$ 结点数 = $2 h_1 + d_1$。

3.5 另一种情况

可能直径是一个端点在 $T^{m-1}$ 内部（非叶子），另一个端点在新子树的最深叶子。 长度 = $H + h_1$（因为从 $T^{m-1}$ 的根到最深叶子 $H$，再接新子树的最深叶子 $h_1$，但这样会重复计算叶子？ 要小心）。

实际上，从 $T^{m-1}$ 的根到新子树最深叶子的结点数 = $H + h_1 - 1$？ 我们来算： 路径：根 -> ... -> 叶子L (H个结点) -> T^1的根 -> ... -> 最深叶子 (h_1个结点)，但叶子L和T^1的根是不同结点，所以总结点数 = H + h_1。

所以这种情况长度 = $H + h_1$。

3.6 递推公式

设 $d_m$ = $T^m$ 的直径（结点数）， $H_m$ = $T^m$ 中从根到最深叶子的结点数。

初始： $d_1$ = $T^1$ 的直径， $H_1$ = $T^1$ 的高度（结点数）。

递推：

情况 A：直径完全在 $T^{m-1}$ 内部：$d_{m-1}$。

情况 B：直径跨两个新子树：$d_1 + 2 h_1$？ 不对，上面我们得到 $d_{m-1} + 2 h_1$？ 检查： 我们取 $T^{m-1}$ 的直径端点 $u,v$（叶子），它们下面接 $T^1$，则新路径长 = $d_{m-1} + 2 h_1$？ 不对，上面算的是 $2 h_1 + d_{m-1}$？ 再检查： $A$ 到 $B$ 结点数 = $h_1$ (A到u) + $d_{m-1}$ (u到v) + $h_1$ (v到B) = $2 h_1 + d_{m-1}$。 但 $A$ 到 $u$ 是 $h_1$ 个结点？ 不对，$A$ 到 $u$ 结点数 = $h_1 + 1$（见前推导），所以总 = $(h_1+1) + d_{m-1} + (h_1+1) - 1$（因为u和v重复计算了一次）？ 我们画图：

路径: $A$ (新子树1最深) -> ... -> $r_u$ (T^1根) -> $u$ (T^{m-1}叶) -> ... -> $v$ (T^{m-1}叶) -> $r_v$ (T^1根) -> ... -> $B$ (新子树2最深)。

结点数 = $h_1$ (A到u) + $d_{m-1}$ (u到v) + $h_1$ (v到B) - 1？ 因为u和v算了两次？ 我们按结点序列数：

A到u: A, ..., r_u, u 共 $h_1+1$ 个结点。 u到v: u, ..., v 共 $d_{m-1}$ 个结点（因为u,v是直径端点）。 v到B: v, r_v, ..., B 共 $h_1+1$ 个结点。

拼接：A...u...v...B，u和v各出现一次，所以总 = $(h_1+1) + (d_{m-1} - 2) + (h_1+1) = 2 h_1 + d_{m-1}$。

好，所以情况 B 长度 = $2 h_1 + d_{m-1}$。

情况 C：直径从 $T^{m-1}$ 的根到新子树最深叶子：长度 = $H_{m-1} + h_1$。

所以：

$$d_m = \max(d_{m-1},\ 2h_1 + d_{m-1},\ H_{m-1} + h_1) $$

显然 $2 h_1 + d_{m-1} \ge d_{m-1}$，所以 $d_m = \max(2 h_1 + d_{m-1},\ H_{m-1} + h_1)$。

3.7 $H_m$ 的递推

$T^m$ 的根到最深叶子的路径： = $T^{m-1}$ 的根到最深叶子（$H_{m-1}$ 个结点） + 该叶子下接的 $T^1$ 的根到最深叶子（$h_1$ 个结点） - 1（重复计算该叶子）？ 不对，应该是 $H_{m-1} + h_1 - 1$？ 检查：

路径：根(T^{m-1}) -> ... -> 叶子L (H_{m-1}个结点) -> 根(T^1) -> ... -> 最深叶子(h_1个结点)。 叶子L和根(T^1)是不同结点，所以总 = $H_{m-1} + h_1$。

所以 $H_m = H_{m-1} + h_1$。

初始 $H_1 = h_1$（$T^1$ 的高度）。

因此 $H_m = m \cdot h_1$。

3.8 最终递推

$d_1$ 已知（输入树的直径）， $h_1$ 已知（输入树的高度，根深度1）。

递推：

$$d_m = \max(2h_1 + d_{m-1}, H_{m-1} + h_1)$$

其中 $H_{m-1} = (m-1) h_1$。

所以：

$$d_m = \max( 2h_1 + d_{m-1},\ m h_1 )$$

初始 $d_1$ 已知。

3.9 解递推

递推式：

$$d_m = \max(2h_1 + d_{m-1},\ mh_1)$$

$d_1$ 已知。

如果 $d_1 \ge h_1$，观察： $d_2 = \max(2 h_1 + d_1,\ 2 h_1) = 2 h_1 + d_1$（因为 $d_1 \ge h_1 > 0$）。 $d_3 = \max(2 h_1 + d_2,\ 3 h_1) = \max(2 h_1 + 2 h_1 + d_1,\ 3 h_1) = \max(4 h_1 + d_1,\ 3 h_1)$。 因为 $d_1 \ge h_1$，$4 h_1 + d_1 \ge 5 h_1 > 3 h_1$，所以 $d_3 = 4 h_1 + d_1$。

模式：$d_m = 2(m-1) h_1 + d_1$？ 检查 m=2: $2\cdot 1 h_1 + d_1 = 2 h_1 + d_1$ 对。 m=3: $4 h_1 + d_1$ 对。

所以通解：

$d_m = d_1 + 2(m - 1)h$,如果 $$d_1 \geq h_1$

如果 $d_1 < h_1$，则可能后来被 $m h_1$ 超过。 但 $d_1$ 是输入树的直径，$h_1$ 是输入树的高度，一般 $d_1 \ge 2 h_1 - 1$？ 不一定，比如链：高度=h，直径=h，所以 $d_1 = h_1$。 那么 $d_1 \ge h_1$ 总是成立？ 因为直径至少等于高度（根到最深叶子）。 所以 $d_1 \ge h_1$。

因此最终：

$$d_m = d_1 + 2(m-1)h_1$$

---

4. 算法步骤

读入 $n, m$ 和父数组。

建树 $T^1$。

求 $T^1$ 的直径 $d_1$（结点数）。

求 $T^1$ 的高度 $h_1$（从根到最深叶子的结点数，根深度1）。

输出 $d_1 + 2(m-1) h_1$。

时间复杂度 $O(n)$。

---

5. 最终公式

$$d_m = d_1 + 2(m-1)h_1$$

其中 $d_1$ 是 $T^1$ 的直径（结点数），$h_1$ 是 $T^1$ 的高度（结点数，根深度为1）。