codeforces #428 div2 C. Journey

問題ページ
Problem - C - Codeforces

考えたこと

• s8pcで見た D - Driving on a Tree
• 1頂点から求めればいいだけなのでもっと簡単
• 頂点1を根とした木について考える
• 止まる頂点は葉以外ありえない
• 葉までの距離とその葉にたどりつく確率を求めれば期待値が求まる
• 葉までの距離はdfsすればいいだけなので簡単
• 頂点vにたどり着く可能性がpで頂点vの子がr_1,r_2,…,r_kならこれらの子にたどり着く確率はp/kになる
• 根から順番に探索していけばいいのでこれもdfsでできる

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

double dp[100010];
int dist[100010];
VI g[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].PB(b);
    g[b].PB(a);
  }

  function<void(int,int,int,double)>
  dfs = [&](int v, int p, int d, double prob) {
    dist[v] = d;
    dp[v] = prob;
    for(int &to: g[v]) if(to != p) {
      int num = (p==-1?g[v].size():g[v].size()-1);
      dfs(to, v, d+1, prob/num);
    }
  };
  dfs(0, -1, 0, 1);

  double ret = 0;
  FOR(i, 1, n) if(g[i].size() == 1) ret += dist[i]*dp[i];
  cout << fixed << setprecision(9) << ret << endl;

  return 0;
}