Description
某个公司有n个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他
下属(直接或者间接, 不包括他自己)中叛徒占的比例超过x，那么这个人也会变成叛徒，并且他的所有下属都会变
成叛徒。你要求出一个最小的x，使得最坏情况下，叛徒的个数不会超过k。
Input
第一行包含两个正整数n,k(1<=k<=n<=500000)。
接下来n-1行，第i行包含一个正整数p[i+1]，表示i+1的父亲是p[i+1](1<=p[i+1]<=i)。
Output
输出一行一个实数x，误差在10^-6以内都被认为是正确的。
Sample Input
9 3
1
1
2
2
2
3
7
3
1
1
2
2
2
3
7
3
Sample Output
0.6666666667
HINT
答案中的x实际上是一个无限趋近于2/3但是小于2/3的数
因为当x取2/3时，最坏情况下3，7，8，9都是叛徒，超过了k=3。
首先我们想一下他最后会形成什么样的情况，很容易发现，到最后叛变的是一个人以及他的所有子树部分
然后我们二分一个值，在每个叶子节点都让他叛变，如果能向上传则向上传，而对于每个点我们选它已经叛变的最大子树
看它能否让这个子树继续叛变，最后记录一下最大值即可
由于他的特殊的连边方式，我们甚至不用每次$DFS$即可完成$check$
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define eps 1e-8 5 #define M 500010 6 using namespace std; 7 int n,k;double l,r,ans; 8 int size[M],fa[M],maxn[M]; 9 bool check(double mid) { 10 memset(maxn,0,sizeof(maxn)); 11 for(int i=n;i>=1;i--) { 12 if(size[i]) { 13 if(maxn[i]/(double)size[i]-mid>eps) maxn[i]=size[i]+1; 14 } 15 maxn[i]=max(maxn[i],1); 16 maxn[fa[i]]=max(maxn[fa[i]],maxn[i]); 17 } 18 if(maxn[1]<=k) return true; 19 return false; 20 } 21 int main() { 22 scanf("%d%d",&n,&k); 23 for(int i=1;i<=n;i++) size[i]=1; 24 for(int i=2,x;i<=n;i++) scanf("%d",&fa[i]); 25 for(int i=n;i>=1;i--) size[fa[i]]+=size[i]; 26 for(int i=1;i<=n;i++) size[i]--; 27 l=0,r=1.0; 28 while(r-l>=eps) { 29 double mid=(r+l)/2.0; 30 if(check(mid)) r=mid; 31 else l=mid; 32 } 33 printf("%.6lf ",l); 34 return 0; 35 }