Journey | Editorial by modi

Journey | Editorial by modi_nitin13

1. Simply use BFS to solve the problem.
2. Make a adjacency list for making the tree.
3. Make a distance array to maintain distance of nodes,Also make a probability array to have probability of reaching any node.
4. **NOTE** if from a point if road diverges in N ways then probability of going in any way is probability of point divided by N.
5. To get the answer have sum of product of distance of leaf node to their probabilities.
6. That's All.
7. **LIKE THE EDITORIAL IF YOU FIND IT GOOD**  
8. Here's the code attached for reference.

```
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define ld long double
#define usll unsigned  int
#define pb push_back
#define boost ios_base::sync_with_stdio(false); cin.tie(NULL);
int main()
{
    ll n,i,x,y;
    cin>>n;
    vector<ll> adj[n];
    ll dist[n];
    bool visited[n]={false};
    ld prob[n];
    for(i=0;i<n-1;i++)
    {
       cin>>x>>y;
       adj[x-1].pb(y-1);
       adj[y-1].pb(x-1);
    }
    prob[0]=1;
    dist[0]=0;
    queue<ll> q;
    q.push(0);
    visited[0]=true;
    ld count=0;
    ll s;
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        for(i=0;i<adj[s].size();i++)
        {
            if(visited[adj[s][i]]==false)
            {
                q.push(adj[s][i]);
                dist[adj[s][i]]=dist[s]+1;
                visited[adj[s][i]]=true;
                if(s==0)
                prob[adj[s][i]]=prob[s]/adj[s].size();
                else
                  prob[adj[s][i]]=prob[s]/(adj[s].size()-1);
            }
        }
        if(adj[s].size()==1)
        count=count+prob[s]*dist[s];
    }
    cout<<setprecision(15)<<count<<endl;
}
```

Journey | Editorial by modi_nitin13

Download submission

All caught up!

View submission

Is your resume even shortlisted?