Submission #1661930

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define MP(a,b) make_pair(a,b)
typedef long long LL;
typedef pair<int, int> PI;
typedef vector<int> VI;
const LL MOD = 1000000007LL;
vector<int> G[150000];
double dp[150000];
double dp2[150000];
void dfs1(int v, int par) {
	int cnt = 0;
	rep(i, G[v].size()) {
		int to = G[v][i];
		if (to == par) continue;
		dfs1(to, v);
		dp[v] += (dp[to] + 1);
		cnt++;
	}
	if (cnt > 0) dp[v] /= cnt;
}
void dfs2(int v, int d_par, int par) {
	rep(i, G[v].size()) {
		int to = G[v][i];
		if (to == par) dp2[v] += (d_par + 1);
		else dp2[v] += (dp[to] + 1);
	}
	rep(i, G[v].size()) {
		int to = G[v][i];
		if (to == par) continue;
		double D = dp2[v] - (dp[to] + 1);
		if (G[v].size() > 1) D /= (G[v].size() - 1);
		dfs2(to, D, v);
	}
	dp2[v] /= G[v].size();
}
int main() {
	int N;
	cin >> N;
	rep(i, N - 1) {
		int u, v;
		cin >> u >> v; u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(0, -1);
	dfs2(0, 0, -1);
	rep(i, N) {
		printf("%.15lf\n", dp2[i]);
	}
}

Submission Info

Judge Result