2015年8月31日 星期一

2015/08/31 HDU 5425 Rikka with Tree II

/*
    觀察到N很大的時候
    距離近的是前二大的機率
    實在太小了 可以直接忽略不算

    另外就是N要足夠大時
    分母才能直接作為2的冪次
    否則需要乖乖算
*/
// http://acm.hdu.edu.cn/showproblem.php?pid=5425
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int N;
vector<int> v[200000];
int d[200000];

void DFS(int O, int x)
{
    d[O] = x;

    for(int vi = 0; vi < v[O].size(); vi++)
        DFS(v[O][vi], x+1);
}

int main()
{

    while( scanf("%d", &N) != EOF )
    {
        for(int Ni = 1; Ni <= N; Ni++) v[Ni].clear();

        for(int Ni = 2; Ni <= N; Ni++)
        {
            int a;
            scanf("%d", &a);
            v[a].push_back(Ni);
        }

        DFS(1, 0);

        sort(d+1, d+N+1, greater<int>() );

        double ans = 0;

        if( N <= 30 )
        {
            for(int j = 1; j <= N; j++)
                for(int i = 1; i < j; i++)
                {
                    double f = d[i], g = d[j];
                    double h = (f+1)*(g+1)/(f+1+g+1);

                    ans += h*(1<<N-j)/((1<<N)-N-1 );
                }
        }
        else
        {
            double val = 1;

            for(int j = 1; j <= min(N,1000); j++)
            {
                val /= 2;

                for(int i = 1; i < j; i++)
                {
                    double f = d[i], g = d[j];
                    double h = (f+1)*(g+1)/(f+1+g+1);

                    ans += h*val;
                }
            }

        }

        printf("%.6f\n", ans);
    }
}

沒有留言:

張貼留言