Submission #1321744

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>

using namespace std;

int n;
vector<vector<int>> edges(150000 + 10);

void read() {
    cin >> n;
    for(int i = 1; i <= n - 1; i++) {

        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
}

int par[150000 + 10], co[150000 + 10];
double expected[150000 + 10], result[150000 + 10];

double dfs(int node, int parent) {
    par[node] = parent;
    for(int son : edges[node]) {
        if(son != parent)
        dfs(son, node);
    }
    for(int son : edges[node]) {
        if(son != parent) {
                co[node]++;
        }
    }
    if(co[node])
    for(int son : edges[node]) {
        if(son != parent)
        expected[node] += (1 + expected[son]) / (double)co[node];
    }
}


void dfs1(int node, int parent) {
    if(node == 1) {
        result[1] = expected[1];
    }
    else{
    result[node] = ((double) co[node]/ ((double) (co[node] + 1))) * expected[node];
    if(par[node] != 1) {
        double res = (double) result[par[node]] * (co[par[node]] + 1) - expected[node] - 1;
        res = res / (double)(co[par[node]]);
        res++;
        result[node] += 1/((double)(co[node] + 1)) * res;
    } else {
        if(par[node] == 1 && co[1] >= 2) {
            double res = (double) result[par[node]] * (co[par[node]]) - expected[node] - 1;
            res = res / (double)(co[par[node]] - 1);
            res++;
            result[node] += 1/((double)(co[node] + 1)) * res;
        } else {
            result[node] += 1/(double)(1 + co[node]);
        }
    }
    }
    for(int i : edges[node]) {
        if(i != parent) {
            dfs1(i, node);
        }
    }
}

void solve() {
    dfs1(1, 0);
    for(int i = 1; i <= n; i++) {
        cout << setprecision(15) << result[i] << endl;
    }

}

int main()
{
    read();
    dfs(1, 0);
    solve();
    return 0;
}

Submission Info

Judge Result