Skip to content

1273: 分形树

题目

题目描述

给定一棵包含 $n$ 个节点的树 $T^1$。现在，如果我们已知树 $T^{m-1}$ 的形态，可以在 $T^{m-1}$ 这棵树的每一个叶子节点的下方接一个树 $T^1$ （以1为根）获得树 $T^m$。注意，根节点也可以是叶子节点。下图是一个很好的例子：

你需要做的就是求出 $T^m$ 的直径长度，也就是树上最远的两个点的路径上（含端点）的节点个数。

输入格式

第一行 $n, m$。

第二行 $p_2, \cdots p_n$，$p_i$ 表示节点 $i$ 与节点 $p_i$ 有边相连。

输出格式

输出一行一个整数，表示答案。

样例输入

text 4 2 1 1 2

样例输出

text 10

数据范围

时间限制：250 ms 空间限制：512 mb

全局限制

  • $3 \leq n \leq 2\times 10^5$
  • $1 \leq m \leq 2\times 10^5$
  • $1 \leq p_i\leq i - 1$

部分限制

  • $(\text{19 points})~ 3\leq n\leq 5000, m = 1$
  • $(\text{10 points})~ m = 1$
  • $(\text{20 points})~ 3\leq n \leq 5000, 1\leq m \leq 5000$
  • $(\text{19 points})~ 3\leq n \leq 5000$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！