Journey

http://codeforces.com/contest/839/problem/C

题目大意：

无向图   n个点   n-1条边    类似与树结构    从1开始到各叶子节点的期望长度     从一个点到其相邻节点的概率相同

分析：

dfs求    到达叶子节点用路长乘以概率就行

AC代码：

#include <bits/stdc++.h>  
#define gcd(a,b) __gcd(a,b)  
#define mset(a,x) memset(a,x,sizeof(a))  
#define FIN     freopen("jogging.in","r",stdin)  
#define FOUT    freopen("jogging.out","w",stdout)  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
const int MAX=1e5+10;  
typedef long long LL;  
const LL mod=1e9+7;  
using namespace std;  
int cnt;
int vis[100005];  
int head[100005];
int inedge[100005];
double ans;
void init(){ 
	ans=cnt=0;
	mset(head,-1);mset(inedge,0);
	mset(vis,0);
}
struct edge{
	int next;
	int to;
}edge[200005];
void add(int u,int v){
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void dfs(int u,int countx,double p){
	int sum=0;
	for (int i=head[u];i!=-1;i=edge[i].next)
		if (!vis[edge[i].to]) sum++;
	if (!sum){
		ans+=countx*p;
		return;	
	}
	for (int i=head[u];i!=-1;i=edge[i].next){
		if (!vis[edge[i].to]){
			vis[edge[i].to]=1;
			dfs(edge[i].to,countx+1,p/sum);
		}
	}
}
int main(){
	int n;
	while (scanf ("%d",&n)!=EOF){
		init();
		int x,y;
		for (int i=1;i<n;i++){
			scanf ("%d%d",&x,&y);
			add(x,y);add(y,x);
			inedge[y]=1;
		}	
		vis[1]=1;
		dfs(1,0,1);
		printf ("%.15lf\n",ans);
	}
	return 0; 
}