Problem Description

A company has $n$ people, and the superior-subordinate relationships form a rooted tree. There is one traitor (it is unknown who it is).

For a person, if among their subordinates (direct or indirect, not including themself), the proportion of traitors exceeds $x$, then this person will also become a traitor, and all of their subordinates will become traitors as well. You need to find the minimum $x$ such that, in the worst case, the number of traitors will not exceed $k$.

Input Format

The first line contains two positive integers $n, k$.

In the next $n - 1$ lines, the $i$-th line contains a positive integer $p_{i+1}$, meaning that the parent of $i + 1$ is $p_{i+1}$.

Output Format

Output one real number $x$. Any answer with an absolute or relative error within $10^{-6}$ is accepted.

9 3
1
1
2
2
2
3
7
3

0.6666666667

Hint

Sample Explanation

In the answer, $x$ is actually a number that approaches $\frac{2}{3}$ infinitely closely but is greater than $\frac{2}{3}$.

Because when $x = \frac{2}{3}$, in the worst case, $3, 7, 8, 9$ are all traitors, which exceeds $k = 3$.

Constraints

For $100\%$ of the testdata, $1 \le k \le n \le 500000$, $1 \le p_{i+1} \le i$.

Translated by ChatGPT 5