839C

839C - Journey

题意：

题解：dfs

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=100010;
 5 struct Edge{
 6     int v,nex;
 7 }e[maxn<<1];
 8 int head[maxn];
 9 int cnt=0;
10 void init(){
11     memset(head,-1,sizeof(head));
12     cnt=0;
13 }
14 void add(int u,int v){
15     e[cnt].v=v;
16     e[cnt].nex=head[u];
17     head[u]=cnt++;
18 }
19 double ans;
20 
21 int deg[maxn];  //无重边的情况下直接记录度数就可以确定儿子了
22 void dfs(int u,int f,int d,double p){
23     for(int i=head[u];~i;i=e[i].nex){
24         int v=e[i].v;
25         if(v==f) continue;
26         if(deg[v]==1) {ans+=(d+1)*p;continue;}
27         dfs(v,u,d+1,p*1.0/(deg[v]-1));
28     }
29 
30 }
31 int main(){
32     int n;
33     scanf("%d",&n);
34     init();
35     int u,v;
36     for(int i=1;i<n;i++){
37         scanf("%d%d",&u,&v);
38         add(u,v);add(v,u);
39         deg[u]++;deg[v]++;
40     }
41     ans=0;
42     dfs(1,0,0,1.0/deg[1]);
43     printf("%lf
",ans);
44 }

View Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=100010;
 5 struct Edge{
 6     int v,nex;
 7 }e[maxn<<1];
 8 int head[maxn];
 9 int cnt=0;
10 void init(){
11     memset(head,-1,sizeof(head));
12     cnt=0;
13 }
14 void add(int u,int v){
15     e[cnt].v=v;
16     e[cnt].nex=head[u];
17     head[u]=cnt++;
18 }
19 double ans;
20 int son[maxn];
21 
22 void dfs1(int u,int f){
23     for(int i=head[u];~i;i=e[i].nex){
24         int v=e[i].v;
25         if(v==f) continue;
26         son[u]++;
27         dfs1(v,u);
28     }
29 }
30 void dfs(int u,int f,int d,double p){
31     for(int i=head[u];~i;i=e[i].nex){
32         int v=e[i].v;
33         if(v==f) continue;
34         dfs(v,u,d+1,p*1.0/son[u]);
35     }
36     if(son[u]==0) {
37         ans+=d*p;
38     }
39 }
40 
41 int main(){
42     int n;
43     scanf("%d",&n);
44     init();
45     int u,v;
46     for(int i=1;i<n;i++){
47         scanf("%d%d",&u,&v);
48         add(u,v);
49         add(v,u);
50     }
51     ans=0;
52     dfs1(1,0);
53     dfs(1,0,0,1);
54     printf("%lf
",ans);
55 }

View Code