fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. vector<int>vec[100005];
  5. bool visit[100005];
  6. double sum=0.0;
  7.  void dfs(int root, double prob,double dist,int prt)
  8.  {
  9.  
  10.  	visit[root]=true;
  11.  	int n=vec[root].size();
  12.  //	cout<<root<<"  "<<dist<<"   "<<prob<<endl;
  13.  	if(n==1)
  14.  	{
  15.  
  16.  		sum+=(prob*dist);
  17.  
  18.  	}
  19.  	else
  20.  	{
  21.  
  22.  		for(int i=0;i<n;i++)
  23.  		{
  24.  
  25.  			if(!visit[vec[root][i]])
  26.  			{
  27.  
  28.  				dfs(vec[root][i],prob/double(n-1),dist+1,root);	
  29.  
  30.  			}
  31.  
  32.  
  33.  		}
  34.  
  35.  
  36.  	}
  37.  
  38.  	return ;
  39.  
  40.  
  41.  }
  42.  int main()
  43.  {
  44.  
  45.  	int n;
  46.  	cin>>n;
  47.  	vec[1].pb(1);
  48.  	for(int i=0,u,v;i<n-1;i++)
  49.  	{
  50.  
  51.  		cin>>u>>v;
  52.  		vec[u].pb(v);
  53.  		vec[v].pb(u);
  54.  
  55.  	}
  56.  	memset(visit,false, sizeof visit);
  57.  	dfs(1,1,0,-1);
  58.  	cout<<setprecision(10)<<fixed<<sum;
  59.  
  60.  
  61.  
  62.  
  63.  }
Success #stdin #stdout 0s 17680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000000
https://ideone.com/1eV9w5
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!