Submission #1573958

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> g;
using ll = long long;
ll mp(int x, int y) {
    return (ll)x << 32 | y & 0xFFFFFFFF;
}
map<ll, double> dp;


double rec(int u, int p) {
    if (dp.count(mp(u, p))) {
        return dp[mp(u, p)];
    }
    double &res = dp[mp(u, p)];
    res = 0;
    int cnt = 0;
    for (auto &v : g[u]) {
        if (v != p) ++cnt;
    }
    if (cnt == 0) {
        res = 0;
    } else {
        for (auto &v : g[u]) {
            if (v != p) {
                res += 1 + rec(v, u);
            }
        }
        res /= cnt;
    }
    return res;
}

int main() {
    while (cin >> n) {
        dp.clear();
        g.assign(n, {});
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        for (int i = 0; i < n; i++) {
            printf("%.10f\n", rec(i, -1));
        }
    }
}

Submission Info

Judge Result