839C. Journey - Codeforces Solution C++

  Problem Link : 839C. Journey 


✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

long double ans;

void avgJourney(int parent,int v,vector<int> adj[],int n,long double p,long double d)
{
	int s = adj[v].size();
	if(v!=1 && s==1)
	{
		ans+=p*d;
		return ;
	}
    
    if(v!=1)
	    s--;

	p = p / s ;

	for(int i=0;i<adj[v].size();i++)
	{
		if(adj[v][i]!=parent)
		{
			avgJourney(v,adj[v][i],adj,n,p,d+1.0);
		}
	}



}

int main()
{
	int n;
	cin>>n;
	vector<int> adj[n+1];
	int u,v;
	for(int i=1;i<=n-1;i++)
	{
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	ans=0.0;

	avgJourney(-1,1,adj,n,1,0.0);

	cout<<setprecision(6)<<fixed<<ans;



}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!