fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. vector<int>x[180000], Z, y[180000], z[180000];
  6. int n, a[180000], b[180000], dist[180000]; long double dp[180000], dp2[180000];
  7. void dfs(int pos, int rec) {
  8. 	if (dist[pos] != 999999999)return;
  9. 	dist[pos] = rec; Z.push_back(pos);
  10. 	for (int i = 0; i < x[pos].size(); i++) {
  11. 		dfs(x[pos][i], rec + 1);
  12. 	}
  13. }
  14. int main() {
  15. 	cin >> n; for (int i = 0; i < n - 1; i++) { cin >> a[i] >> b[i]; x[a[i]].push_back(b[i]); x[b[i]].push_back(a[i]); }
  16. 	//int pos = 1; for (int i = 1; i <= n; i++) { if (x[i].size() == 1)pos = i; }
  17. 	for (int i = 1; i <= n; i++)dist[i] = 999999999; dfs(1, 0);
  18. 	for (int i = 0; i < n - 1; i++) {
  19. 		if (dist[a[i]] > dist[b[i]]) { y[b[i]].push_back(a[i]); z[a[i]].push_back(b[i]); }
  20. 		if (dist[a[i]] < dist[b[i]]) { y[a[i]].push_back(b[i]); z[b[i]].push_back(a[i]); }
  21. 	}
  22. 	if(Z.size()!=n)return 0;
  23. 	if(n<=0 || n>150000)return 0;
  24. 	for (int i = Z.size() - 1; i >= 0; i--) {
  25. 		long double E = 0;
  26. 		for (int j = 0; j < y[Z[i]].size(); j++)E += dp[y[Z[i]][j]] + 1;
  27. 		if (y[Z[i]].size() >= 1) { E /= y[Z[i]].size(); } dp[Z[i]] = E;
  28. 	}
  29. 	for (int i = 0; i < Z.size(); i++) {
  30. 		long double E = 0;
  31. 		for (int j : x[Z[i]]) {
  32. 			if(dist[Z[i]] < dist[j])E += dp[j] + 1;
  33. 			if (dist[Z[i]] > dist[j]) {
  34. 				if (x[j].size() == 1)E += 1;
  35. 				else E += (dp2[j] * x[j].size() - (dp[Z[i]] + 1)) / (x[j].size() - 1) + 1;
  36. 			}
  37. 		}
  38. 		if (x[Z[i]].size() >= 1) { E /= x[Z[i]].size(); }
  39. 		dp2[Z[i]] = E;
  40. 	}
  41. 	for (int i = 1; i <= n; i++) {
  42. 		printf("%.12Lf\n", dp2[i]);
  43. 	}
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 36456KB
comments (?)
stdin
copy 
7
1 2
1 3
2 4
2 5
3 6
3 7
stdout
copy 
2.000000000000
1.666666666667
1.666666666667
3.000000000000
3.000000000000
3.000000000000
3.000000000000
https://ideone.com/HKNcrX
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!