Codeforces 839C [DFS]

题目

839C

题意

有n个城市,n-1条路连通这些城市。骑马从城市1出发,沿道路走到底。

每个分叉点各条路概率相等,不能回头。

求走路长度的期望…

输入

4
1 2
1 3
2 4

输出

1.500000000000000

样例输入

5
1 2
1 3
3 4
2 5

样例输出

2.000000000000000

题解分析

em… 好尴尬,一开始题意理解错了,以为每个根的概率都一样…

做法很简单,简单的DFS而已。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
vector<int> g[100000+3];
int vis[100000+3];
int n;
double res;
void dfs(int x,int s,double d)
{
int len = g[x].size();
int k=0;
for(int i=0;i<len;i++)
{
if(g[x][i]&&!vis[g[x][i]])
{
vis[x] = 1;
dfs(g[x][i],s+1,d/(x==1?len:(len-1)));k=1;
vis[x] = 0;
}
}
if(!k)
{
res += s*d;
return;
}
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
n--;
while(n--)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1,0,1);
printf("%.15lf\n",res);
}