Submission #2560392

---

Source Code Expand

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

const int N = 150000;
vector<pair<int, int>> g[N];
vector<double> expect[N];

double dfs(int i, int p, int t) {
  if(expect[i][t] > -1) return expect[i][t];
  expect[i][t] = 0;
  for(auto edge : g[i]) if(edge.first != p) {
    expect[i][t] += (1 + dfs(edge.first, i, edge.second));
  }
  if(g[i].size() - (p != -1)) expect[i][t] /= (g[i].size() - (p != -1));
  return expect[i][t];
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n;
  cin >> n;
  for(int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b; a--; b--;
    expect[a].emplace_back(-1);
    expect[b].emplace_back(-1);
    g[a].emplace_back(b, expect[b].size() - 1);
    g[b].emplace_back(a, expect[a].size() - 1);
  }
  cout << fixed << setprecision(7);
  for(int i = 0; i < n; i++) {
    expect[i].emplace_back(-1);
    cout << dfs(i, -1, expect[i].size() - 1) << endl;
  }
}

Submission Info

Judge Result