[AdditionalFile4911.zip](file://AdditionalFile4911.zip?type=additional_file)

P5958 [POI 2017] Sabotaż

题目描述

某个公司有 $n$ 个人，上下级关系构成了一个有根树。其中有个人是叛徒（这个人不知道是谁）。

对于一个人，如果他下属（直接或者间接，不包括他自己）中叛徒占的比例超过 $x$，那么这个人也会变成叛徒，并且他的所有下属都会变成叛徒。你要求出一个最小的 $x$，使得最坏情况下，叛徒的个数不会超过 $k$。

输入格式

第一行包含两个正整数 $n,k$。

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

输出格式

输出一行一个实数 $x$，误差在 $10^{-6}$ 以内都认为是正确的。

输入输出样例 #1

输入 #1

9 3
1
1
2
2
2
3
7
3

输出 #1

0.6666666667

说明/提示

样例解释

答案中的 $x$ 实际上是一个无限趋近于 $\frac{2}{3}$ 但是大于 $\frac{2}{3}$ 的数。

因为当 $x$ 取 $\frac{2}{3}$ 时，最坏情况下 $3,7,8,9$ 都是叛徒，超过了 $k=3$。

数据范围

对于 $100\%$ 的数据，$1\le k\le n\le 500000$，$1\le p_{i+1}\le i$。

#4911. 「POI2017 R1」破坏 Sabotage

标签: 传统 | 时间限制: 1500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXIV Olimpiada Informatyczna — I etap Sabotaż

在一个不便透露名称的组织里，上司与下属的关系可以用一棵树来表示——除了最高领导，每个人都有且仅有一个直属上司。员工按入职顺序编号，上司的编号总是小于下属。

监督委员会担心组织内部可能潜伏着破坏者，想挑起员工叛乱。为了防患于未然，他们希望保持员工的高昂士气（比如发奖金、办活动、买桌上足球桌）。士气用一个 $0$ 到 $1$ 之间的实数 $x$ 表示。如果某个员工发现，自己（直接或间接）下属中有超过 $x$ 比例的人叛乱，他也会加入叛乱，并强迫所有直接和间接的下属跟随。破坏者是某个员工，会在某刻率先叛乱（但不强迫下属加入）。

委员会想知道，为了让叛乱最多影响 $k$ 名员工，士气的最小值是多少。请你写个程序帮他们算出来。

输入格式

输入第一行包含两个整数 $n$ 和 $k$ $(1 \leq k \leq n \leq 500000)$，用空格分隔，分别表示员工总数和叛乱人数上限。员工编号从 $1$ 到 $n$，最高领导为 $1$ 号。

接下来的 $n-1$ 行描述组织结构，第 $i$ 行有一个整数 $p_{i}$ $(p_{i} \leq i)$，表示编号为 $i+1$ 的员工的直属上司是 $p_{i}$ 号员工。

输出格式

输出一行一个实数，表示所需的最小士气值。结果与正确答案相差小于 $10^{-6}$ 即视为正确。

样例

输入

9 3
1
1
2
2
2
3
7
3

输出

0.6666666667

士气低于 $\frac{2}{3}$ 时，若 $8$ 号员工是破坏者，他叛乱后会导致 $4$ 人（$3, 7, 8, 9$ 号）叛乱，超过上限 $3$。

附加样例

1. 领导加 $9$ 个直属下属；
2. $20$ 名员工的随机测试；
3. $500000$ 名员工，除最晚入职者外，每人有几个直属下属。

数据范围与提示

详细子任务附加限制及分值如下表所示。