➤ 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!!