Description

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

Input

第一行包含两个正整数 \(n, k (1 \leq k \leq n \leq 500000)\).

接下来 \(n-1\) 行, 第 \(i\) 行包含一个正整数 \(p[i+1]\), 表示 \(i+1\) 的父亲是 \(p[i+1](1 \leq p[i+1] \leq i)\).

Output

输出一行一个实数 \(x\), 误差在 \(10^{-6}\) 以内都被认为是正确的.

Sample Input

9 3
1
1
2
2
2
3
7
3

Sample Output

0.6666666667

Explanation

http://blog.csdn.net/neither_nor/article/details/53373065

首先显然最劣情况初始的叛徒肯定是叶子

并且带头叛变的人一定是从某个叶子往上走一条链

因为如果 \(i\) 没有带头叛变, 那么 i 的父亲也一定不会带头叛变, 证明显然:

\(dp[i]\) 表示 \(i\) 不带头叛变的话最小的 \(x\)

那么我们对所有子树大小 \(\gt k\) 的 \(dp\) 值取 \(max\) 即是答案

\[dp[i] = max(dp[i], min(dp[j],\frac{siz[j]}{siz[i]-1})), j\ \text{is child of}\ i\]

因为对于 \(i\) 的一个儿子 \(j\), 假如 \(i\) 因为 \(j\) 的子树里的叛徒比例大于 \(x\) 而带头叛变, 那么既要满足 $x $(j 的子树大小占 i 的子树大小的比例), 还要满足 \(j\) 带头 叛变即 \(x \leq dp[j]\), 所以对两个量取 \(min\)

那么如果 \(i\) 不叛变, 那么就不能满足任意一个条件, 所以对所有的取 \(max\)

对于叶子,\(dp[i]=1\), 因为不管怎样叶子本身就是叛徒, 可以视为不需要条件就可以带头 叛变, 即只有当 \(x \lt 1\) 时才不会叛变

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 500100;

class TreeDP
{
public:
    struct edge
    {
        int v;
        edge *next;
    };
    int n, K, ecnt;
    edge *edges[maxn], epool[maxn];
    int par[maxn], size[maxn];
    llf dp[maxn];
    void set_child(int p, int q)
    {
        edge *ep = &epool[++ecnt];
        ep->v = q;
        ep->next = edges[p]; edges[p] = ep;
        par[q] = p;
        return ;
    }
    void dfs(int p)
    {
        size[p] = 1;
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            dfs(ep->v);
            size[p] += size[ep->v];
        }
        if (edges[p] == NULL) {
            dp[p] = 1.0;
        } else { // Is not a leaf!
            for (edge *ep = edges[p]; ep; ep = ep->next) {
                dp[p] = max(dp[p], min(1.0 * size[ep->v] / (llf)(size[p]-1), dp[ep->v]));
            }
        }
        return ;
    }
    llf eval(void)
    {
        llf res = 0.0;
        dfs(1);
        for (int i = 1; i <= n; i++)
            if (size[i] > K)
                res = max(res, dp[i]);
        return res;
    }
} td;

int n, K;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    td.n = n;
    td.K = K;
    for (int i = 2; i <= n; i++) {
        int j = 0;
        scanf("%d", &j);
        td.set_child(j, i);
    }
    llf res = td.eval();
    printf("%.8Lf\n", res);
    return 0;
}