Bonus 奖励计划

Time Limit:3000MS Memory Limit:65536K
Total Submit:58 Accepted:16
Case Time Limit:1000MS

Description

Input

请做到文件底结束,对于每一组：
第一行包含一个正整数N，表示城市的数目。
接下来的N-1行，每行包含2个整数，Ai、Bi，表示Ai和Bi间有一条双向的旅行通道。

Output

对于每一组测试数据，输出一行：
为一个实数，表示平均的支付费用，保留（四舍五入）至小数点后6位。

Sample Input

Sample Output

Hint

10%的数据中N ≤ 10；
30%的数据中N ≤ 100；
50%的数据中N ≤ 1000。
100%的数据中2 ≤ N ≤ 10000，T ≤ 10，1 ≤ Ai，Bi ≤ N，Ai≠Bi。
数据保证任意两个城市之间有且只有一条路径（Path）。

Source

北京2010
额。。看上去很难实际上还是挺水滴。。关键是给每条边的边权赋值成这个点被穿过的概率。。那么答案就是所有路径长度的平均值。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
const int inf=~0U>>1,maxn=10000;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>::iterator it;
vector<int> E[maxn];
int n,Size[maxn];
double Ans,Sum[maxn];
void Clear()
{
    rep(i,maxn)E[i].clear();
}

void AddEdge(int s,int t)
{
    E[s].pb(t);E[t].pb(s);
}

bool Init()
{
    Clear();
    if(scanf("%d",&n)!=1)return false;

    int s,t;
    rep(i,n-1)
    {
        scanf("%d%d",&s,&t);
        –s;–t;
        AddEdge(s,t);
    }

    return true;
}
void Dfs(int x,int f)
{
    Size[x]=1;Sum[x]=0;
    tr(e,E[x])if(*e!=f)
    {
        Dfs(*e,x);
        Size[x]+=Size[*e];
    }
    tr(e,E[x])if(*e!=f)
    {
        double c=double(Size[*e])*(n-Size[*e])/(n*(n-1)/2);
        //cout<<(*e)<<"<->"<<x<<":"<<c<<endl;
        Sum[x]+=Size[*e]*c+Sum[*e];
        Ans+=(Size[x]-Size[*e])*(Sum[*e]+c*Size[*e]);
    }
}

void Solve()
{
    Ans=0;
    Dfs(0,-1);
    printf("%0.6lfn",Ans/((n-1)*n/2));
}
int main()
{
    //freopen("in","r",stdin);
    while(Init())Solve();
}

1.0000000.8888890.7500000.84000021 231 22 341 21 31 451 25 22 34 3