HDU4219 Randomization?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 95 Accepted Submission(s): 37

Problem Description

Random is the real life. What we see and sense everyday are absolutely randomly happened. Randomization is the process of making something random, as the nature.
Given a tree with N nodes, to be more precisely, a tree is a graph in which each pair of nodes has and only has one path. All of the edges’ length is a random integer lies in interval [0, L] with equal probability. iSea want to know the probability to form a tree, whose edges’ length are randomly generated in the given interval, and in which the path's length of every two nodes does not exceed S.

Input

The first line contains a single integer T, indicating the number of test cases.
Each test case includes three integers N, L, S. Then N - 1 lines following, each line contains two integers Ai and Bi, describing an edge of the tree.

Technical Specification
1. 1 <= T <= 512
2. 1 <= N <= 64
3. 1 <= L <= 8, 1 <= S <= 512
4. 1 <= Ai, Bi <= N

Output

For each test case, output the case number first, then the probability rounded to six fractional digits.

Sample Input

Sample Output

Case 1: 0.750000
Case 2: 0.500000
Case 3: 0.624832

Author

iSea@WHU

Source

首届华中区程序设计邀请赛暨第十届武汉大学程序设计大赛

********************************************

题目大意：给定一棵树，然后树的边权是[0,L]任意赋值，问这颗树不存在有一条链的长度超过S的概率。

代码：

/*
概率+树形dp
中等偏难题，想概率容易脑乱，静下心来想还是可以出的
dp[以i为根][以j为叶子节点到i的最远距离]
当j*2<=s的时候，表示这个子树上的最长链不可能超过s，那么
可以任意取值就是当前的概率，但是为了保证j是精确的，所以要
减去距离小于等于j-1的概率；
当j*2>s的时候，这个子树必定有且仅有一个链的长度是s，那么
枚举该链，让其他链的长度任意取值，所有情况之和就是概率
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#define N 70
#define S 600
using namespace std;

int n,l,s,vis[N],fa[N];
vector<int>gra[N];
double dp[N][S];

void dfs(int d,int p)
{
    vis[d]=1;fa[d]=p;
    int len=gra[d].size();
    if(p!=-1&&len==1)
    {
        dp[d][0]=1;
        for(int i=1;i<=s;i++)dp[d][i]=0;
        return ;
    }
    for(int i=0;i<len;i++)
        if(!vis[gra[d][i]])dfs(gra[d][i],d);
    double sum[S]={0};
    for(int i=0;i<=s;i++)
    {
        if(i*2<=s)
        {
            dp[d][i]=1;
            for(int j=0;j<len;j++)
            {
                int e=gra[d][j];
                if(fa[e]!=d)continue;
                double tmp=0;
                for(int k=0;k<=min(l,i);k++)
                    for(int h=0;h<=i-k;h++)
                        tmp+=dp[e][h];
                tmp/=(l+1);
                dp[d][i]*=tmp;
            }
            if(i>0)dp[d][i]-=sum[i-1],sum[i]=dp[d][i]+sum[i-1];
            else sum[i]=dp[d][i];
        }
        else
        {
            int op=s-i;
            dp[d][i]=0;
            for(int j=0;j<len;j++)
            {
                int e=gra[d][j];
                if(fa[e]!=d)continue;
                double tmp1=0;
                for(int k=0;k<=min(l,op);k++)
                    for(int h=0;h<=op-k;h++)
                        tmp1+=dp[e][h];
                tmp1/=(l+1);
                double tmp2=0;
                for(int k=0;k<=min(l,i);k++)
                    tmp2+=dp[e][i-k];
                tmp2/=(l+1);
                dp[d][i]+=sum[op]*tmp2/tmp1;
            }
        }
    }
}

int main()
{
    //freopen("/home/fatedayt/in","r",stdin);
    int ncase;
    scanf("%d",&ncase);
    for(int u=1;u<=ncase;u++)
    {
        scanf("%d%d%d",&n,&l,&s);
        for(int i=1;i<=n;i++)gra[i].clear();
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            gra[a].push_back(b);
            gra[b].push_back(a);
        }
        memset(vis,0,sizeof(vis));
        dfs(1,-1);
        double ans=0;
        for(int i=0;i<=s;i++)ans+=dp[1][i];
        printf("Case %d: %.6lf\n",u,ans);
    }
}