839C - Journey

链接：

https://codeforces.com/problemset/problem/839/C

题意：

一棵树，一只动物，他到每个子节点的概率相同

求从树根出发的路径长度期望（每个边长度1）

解：

根节点概率a，有n个子节点，那么子节点概率a/n

*期望=所有叶子节点的（权重[路径长度]概率）

实际代码：

#include<iostream>
#include<bits/stdc++.h>
#define  csh(a) memset(a,0,sizeof(a)) 
using namespace std;
typedef long long int ll;
typedef long double ld;
const int Size=1E5+5;
vector<int>tree[Size];
double QW[Size];
bool book[Size];
ld ans=0;
void add(int u,int v)
{
	tree[u].push_back(v);
	tree[v].push_back(u);
}
int dfs(int G,double level,int deep)
{
	//cout<<"G:"<<G<<" level:"<<level<<" deep"<<deep<<endl;
	book[G]=1;
	if(tree[G].size()==1)
	{
		int i=tree[G][0];
		if(book[i]==1)
		{
			ans=ans+deep*level;
			return 0;
		}
	}
	int num=tree[G].size();
	if(G!=1)num--;
	/*
	for(auto i:tree[G])
	{
		if(book[i]==1) num--;
	}
	*/
	for(auto i:tree[G])
	{
		if(book[i]==1) continue;
		dfs(i,level/(num),deep+1);
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs(1,1.0,0);
	cout<<fixed<<setprecision(15)<<ans<<endl;
}

限制：

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output