CodeForces 839C - Journey | Codeforces Round #428 (Div. 2)

起初误以为到每个叶子的概率一样于是....

/*
CodeForces 839C - Journey [ DFS,期望 ] | Codeforces Round #428 (Div. 2)
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n;
vector<int> G[N];
double dp[N], val[N];
bool vis[N];
void dfs(int u, int pre)
{
bool flag = 0;
for (auto&v : G[u])
{
if (v == pre) continue;
flag = 1;
dp[v] = dp[u]+1;
val[v] = val[u] / (G[u].size()-1);
dfs(v, u);
}
if (!flag) vis[u] = 1;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
G[1].push_back(1);
val[1] = 1;
dfs(1, 1);
int cnt = 0;
double ans = 0;
for (int i = 1; i <= n; i++)
if (vis[i]) ans += dp[i]*val[i];
printf("%.15f\n", ans);
}

  

上一篇:Sublime Text 3中关闭记住上次打开的文件


下一篇:LPC43xx SGPIO Experimentation