[POI2017] Sabotaż

题目描述

某个公司有 $n$ 个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。 对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过 $x$,那么这个人也会变成叛徒,并且他的所有下属都会变成叛徒。你要求出一个最小的 $x$,使得最坏情况下,叛徒的个数不会超过 $k$。

输入输出格式

输入格式


第一行包含两个正整数 $n,k$。 接下来 $n-1$ 行,第 $i$ 行包含一个正整数 $p_{i+1}$,表示 $i+1$ 的父亲是 $p_{i+1}$。

输出格式


输出一行一个实数 $x$,误差在 $10^{-6}$ 以内都被认为是正确的。 **所以本题使用 SPJ。**

输入输出样例

输入样例 #1

9 3
1
1
2
2
2
3
7
3

输出样例 #1

0.6666666667

说明

对于 $100\%$ 的数据,$1\le k\le n\le 500000$,$1\le p_{i+1}\le i$。 ----- ### 样例说明: 答案中的 $x$ 实际上是一个无限趋近于 $\frac{2}{3}$ 但是大于 $\frac{2}{3}$ 的数。 因为当 $x$ 取 $\frac{2}{3}$ 时,最坏情况下 $3,7,8,9$ 都是叛徒,超过了 $k=3$。