BZOJ4726 [POI2017]Sabota?

DarkBzoj提交地址：因为没有SPJ，所以需要特殊处理答案如下：

if (ans) printf("%.10f",ans);
else puts("0");

题意

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

题解

找到最小的 $x$ ，使得叛徒个数不超过 $k$ $=$ 找到最大的 $x$ ，使得叛徒个数大于 $k$ 。

可以发现最后一定是某一棵子树在叛变，用 $f[x]$ 表示使得 $x$ 及其子树叛变的最小比例。用 $siz[x]$ 表示 $x$ 的子树大小，方程式为：

$$f[x]=\max \{\min\{f[y],\dfrac{siz[y]}{siz[x]-1}\}\}$$

将所有 $siz[x] > k$ 的 $f[x]$ 统计进答案。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=500005;
struct Edge {
    int next,to;
} edge[N];
int cnt,head[N],n,m,siz[N];
double ans,f[N];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs1(int x)
{
    siz[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        dfs1(y);
        siz[x]+=siz[y];
    }
}

void dfs2(int x)
{
    if (!head[x]) f[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        dfs2(y);
        f[x]=max(f[x],min(f[y],1.0*siz[y]/(siz[x]-1)));
    }
    if (siz[x]>m) ans=max(ans,f[x]);
}

signed main()
{
    n=read(); m=read();
    for (int i=2;i<=n;i++) add(read(),i);
    dfs1(1);
    dfs2(1);
    return !printf("%.10f",ans);
}