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

第一行包含两个正整数n,k(1<=k<=n<=500000)。

接下来n-1行，第i行包含一个正整数p[i+1]，表示i+1的父亲是p[i+1](1<=p[i+1]<=i)。

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

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

因为当x取2/3时，最坏情况下3，7，8，9都是叛徒，超过了k=3。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 5e5+10;
 6 const double EPS = 1e-8;
 7 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
 8 #define REP_EDGE(i, a) for (int i = (a); i != -1; i = e[i].nxt)
 9 #define mset(a, b) memset(a, b, sizeof(a))
10 int fcmp(double x) { if (x > -EPS && x < EPS) return 0; return x < -EPS ? -1 : 1; }
11 double max_(const double &AI, const double &BI) { return fcmp(AI-BI) == 1 ? AI : BI; }
12 double min_(const double &AI, const double &BI) { return fcmp(AI-BI) == -1 ? AI : BI; }
13 int n, k;
14 struct Edge
15 {
16     int v, nxt;
17     Edge (int v = 0, int nxt = 0): v(v), nxt(nxt) {}
18 }e[maxn];
19 int head[maxn], label, siz[maxn];
20 double f[maxn];
21 
22 void ins(int u, int v) { e[++label] = Edge(v, head[u]), head[u] = label; }
23 
24 void dfs(int u, int fa)
25 {
26     siz[u] = 1;
27     REP_EDGE(i, head[u])
28         if (e[i].v != fa)
29             dfs(e[i].v, u), siz[u] += siz[e[i].v];
30     if (siz[u] == 1) { f[u] = 1.0; return ; }
31     f[u] = 0.0;
32     REP_EDGE(i, head[u])
33         if (e[i].v != fa)
34             f[u] = max_(f[u], min_(1.0*siz[e[i].v]/double(siz[u]-1), f[e[i].v]));
35 }
36 
37 int main()
38 {
39     scanf("%d %d", &n, &k);
40     REP(i, 1, n) head[i] = -1;
41     label = -1;
42     REP(i, 2, n){ int u; scanf("%d", &u), ins(u, i); }
43     dfs(1, 0);
44     double ans = 0.0;
45     REP(i, 1, n)
46         if (siz[i] > k) ans = max_(ans, f[i]);
47     printf("%.8lf\n", ans);
48     return 0;
49 }