General
 
 
# 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
→ Source
#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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details