样例下载

【题目描述】

一棵树含有 $n$ 个节点，编号为 $1$ ~ $n$。其中 $1$ 号节点为根节点。

现在有一个节点发生了腐烂，但并不知道是哪个节点。

对于一个节点 $i$，如果它的所有子孙后代节点中，腐烂的节点所占的比例超过 $p$，那么该节点 $i$ 以及它的所有子孙后代结点全部会发生腐烂。

现在请你计算 $p$ 的最小值，使得在最坏情况下，腐烂的结点个数不超过 $m$。

【输入格式】

第一行：两个整数 $n,m$

接下来 $n-1$ 行：每行一个整数，依次表示 $2$ 号点、$3$ 号点、……、 $n$ 号点的父节点编号。数据保证父节点编号一定小于子节点编号。

【输出格式】

一个实数 p，表示答案，误差在 0.000001 以内均被视为正确的。

【输入样例】

9 3
1
1
2
2
2
3
7
3

【输出样例】

0.6666666667

【样例解释】

答案中的 p 实际上是一个无限趋近于 2/3 但是小于 2/3 的数

因为当 p 取 2/3 时，最坏情况下，编号为 3，7，8，9 的节点都发生了腐烂，超过了 m = 3。

【数据范围】

100% 的数据：$1 ≤ m ≤ n ≤ 5 × 10^5$