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了,可以的话,请您参考添加页面,与大家一起分享你的题解!