Submission #1438961

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
 
#define rep(i, n) for(int i = 0; i < (n); ++i)
 
using namespace std;

typedef long double ld;

int n;
vector<int> t[150000];
bool used[150000];
vector<int> g[150000];
ld e[150000];
ld ans[150000];

void make_graph(int i){
    used[i] = true;
    for(int v: t[i]){
        if(!used[v]){
            g[i].push_back(v);
            make_graph(v);
        }
    }
}

ld dfs(int i){
    ld c = 0;
    for(int v: g[i]){
        c += dfs(v) + 1;
    }
    return e[i] = c / max((int)g[i].size(), 1);
}

void solve(int i, ld u){
    if(i == 0){
        ans[i] = e[i];
        ld s = 0;
        for(int v: g[i]){
            s += e[v];
        }
        for(int v: g[i]){
            solve(v, g[i].size() == 1 ? 0 : (s - e[v]) / (g[i].size() - 1) + 1);
        }
        return;
    }
    ans[i] = (u + 1 + g[i].size() * e[i]) / (g[i].size() + 1);
    ld s = 0;
    for(int v: g[i]){
        s += e[v];
    }
    for(int v: g[i]){
        solve(v, (s - e[v] + u) / g[i].size() + 1);
    }
}

int main(){
    cin >> n;
    rep(i, n - 1){
        int u, v;
        cin >> u >> v;
        t[u - 1].push_back(v - 1);
        t[v - 1].push_back(u - 1);
    }

    make_graph(0);

    dfs(0);

    solve(0, -1);

    rep(i, n){
        cout << fixed << setprecision(10) << ans[i] << endl;
    }
    return 0;
}

Submission Info

Judge Result