P5958 [POI 2017] Sabotage

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$.

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 one real number $x$. Any answer with an absolute or relative error within $10^{-6}$ is accepted.

#### 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