CF 839B Journey

//Explanation

After going to each leaf node, calculate xi*pi i.e. len * probability at each level. from a node, multiple branch can be selected so, 1/branches probability needs to be multiplied at each level. so from node 1, we shall get the expected len of travelling to any leaf node after summing at the same level and multiple level also.

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define all(x) (x).begin(),(x).end()
#define mem(a,d) memset(a,d,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 12345678912

int vis[100007];
int d[100007];
vector<int> adj[100007];

double dfs(int u)
{
    vis[u] = 1;

    double levelsum= 0;
    int adjs = 0;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];
        if(vis[v]==0)
        {
            adjs++;
            d[v] = d[u] + 1;
            levelsum += dfs(v);
        }
    }
    if(adjs==0) return d[u];
    else
        return levelsum *(1.0/adjs) ;
}


int main()
{
    ll u,v,n,e,st;
    cin>>n;

    FOR(i,1,n-1)
    {
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    double ans = dfs(1);

    printf("%.15f\n", ans);

    return 0;
}