链接：http://codeforces.com/contest/839/problem/C
C. Journey
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n cities and n - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads.

Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren’t before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities.

Let the length of each road be 1. The journey starts in the city 1. What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link https://en.wikipedia.org/wiki/Expected_value.

Input
The first line contains a single integer n (1 ≤ n ≤ 100000) — number of cities.

Then n - 1 lines follow. The i-th line of these lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the cities connected by the i-th road.

It is guaranteed that one can reach any city from any other by the roads.

Output
Print a number — the expected length of their journey. The journey starts in the city 1.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let’s assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Examples
input
4
1 2
1 3
2 4
output
1.500000000000000
input
5
1 2
1 3
3 4
2 5
output
2.000000000000000
Note
In the first sample, their journey may end in cities 3 or 4 with equal probability. The distance to city 3 is 1 and to city 4 is 2, so the expected length is 1.5.

In the second sample, their journey may end in city 4 or 5. The distance to the both cities is 2, so the expected length is 2.
百度翻译题意：

··
有N个城市和N - 1路七国，每路连接了两个城市，我们可以到达任何城市任何其他的道路。
席恩和Yara Greyjoy是在第一城的马，他们开始穿越公路。但是天气多雾，所以他们看不见马把他们带到哪儿了。当马到达一个城市（包括第一个城市），它会转到一个与当前城市相连的城市。但是它是一匹奇怪的马，它只去那些以前没有的城市。在每一个这样的城市里，马都有相同的概率，如果没有这样的城市，它就会停下来。
让每一条路的长度是1。1在城市开始旅程。他们旅程的预期长度（期望值）是多少？您可以通过链接读取关于期望值（平均值）的信息。
··

题目大意：
给一棵树，结点1为根，每条边长为1，从根出发，每到一个结点，可等概率的往其子树走，到叶子则终止，求走过的路径长度的期望。
分析：
这个题手算和用程序写出来是不一样的,首先n个点n-1条边且任意两点联通，所以这个图是一个无向树，这样要保证走过的路不再走只要保证走的下一条边不是他的父亲节点即可，那么对于每个节点如何计算呢？

    对于单个节点我们可以看出，除非它没有子节点，否则无论有几个字节点，它下一步的期望一定是1。


对于上图的两个树来说，我们手动计算他们的期望发现，都是2， 


   对于其中的2节点来说，除了他自身带的概率，自身到下一步的概率依然是1，所以我们计算单个节点概率的公式就是
 if(该节点非叶子结点） p  =1.0+sum (子节点的概率之和)/ k（子节点个数）

code:

#include <iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n;
vector<int>o[101000];
double dfs(int x,int father)
{
    double sum  =0.0,k=0.0;
    int flag = 0;//判断是不是叶子结点
    for(int i=0;i<o[x].size();i++)
    {
        int v =o[x][i];
        if(v==father)continue;//判断是否走回父节点
        k+=1.0;
        flag = 1;
        sum+=dfs(v,x);
    }
    if(flag) return 1.0+sum/k;
    else return 0.0;

}
int main(){

    cin>>n;
    int a,b;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&a,&b);
        o[a].push_back(b);
        o[b].push_back(a);
    }
    printf("%.7lf",dfs(1,0));
    return 0;
}