# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
76082689 |
Practice:
Karan123 |
839C
- 36
|
GNU C++11
|
Wrong answer on test 6
|
343 ms
|
4968 KB
|
2020-04-10 14:18:31 |
2020-04-10 14:18:31 |
|
#include<bits/stdc++.h>
using namespace std;
#define N 100001
vector<vector<long int>>a(N);
vector<long double>prob(N);
vector<long int>steps(N);
vector<long int>visited(N);
int dfs(int index){
if(visited[index]==1)
return 0;
int i;
// cout<<"index:"<<index<<"\n";
visited[index]=1;
for(i=0;i<a[index].size();i++){
// cout<<"Child:"<<a[index][i]<<"a[index].size():"<<a[index].size()<<"\n";
if(visited[a[index][i]]==0){
if(index==0)
prob[a[index][i]] = prob[index]*(1.0/(a[index].size()));
else
prob[a[index][i]] = prob[index]*(1.0/(a[index].size()-1));
steps[a[index][i]] = steps[index]+1;
// cout<<"steps:"<<steps[a[index][i]]<<"prob:"<<prob[a[index][i]]<<"\n";
dfs(a[index][i]);}
}
return 0;
}
int main(){
int n;
cin>>n;
int i,x,y,j;
prob[0]=1;
for(i=0;i<n-1;i++){
cin>>x>>y;
a[x-1].push_back(y-1);
a[y-1].push_back(x-1);
// cout<<"i:"<<i<<"x:"<<x<<"y:"<<y<<"\n";
}
// cout<<"Array:\n";
// for(i=0;i<n;i++){
// for(j=0;j<a[i].size();j++)
// cout<<a[i][j]<<" ";
// cout<<"\n";
// }
// cout<<"\n***********\n";
dfs(0);
long double sum = 0;
for(i=0;i<n;i++){
if(a[i].size()==1){
sum = sum + steps[i]*prob[i];
}
}
// for(i=0;i<n;i++){
// cout<<"i:"<<i+1<<"prob[i]:"<<prob[i]<<"steps[i]:"<<steps[i]<<"\n";
// }
cout<<setprecision(6)<<sum;
return 0;
}
Click to see test details