Advertisement
Josif_tepe

Untitled

Oct 19th, 2023
711
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. const int max_=100000;
  5. double ans=0;
  6. vector<int>v[max_];
  7. void dfs(int at, int parent, double probabilty, int d){
  8. int b=0;
  9. for(int i:v[at]){
  10.     if(i!=parent){
  11.         b++;
  12.     }
  13. }
  14. for(int i:v[at]){
  15.     if(i!=parent){
  16.         dfs(i, at, probabilty/b, d+1);
  17.     }
  18. }
  19. if(b==0){
  20.     ans+=probabilty*d;
  21. }
  22. }
  23. int main()
  24. {
  25.      cin>>n;
  26.      for(int i=0; i<n-1; i++){
  27.         int a,b;
  28.         cin>>a>>b;
  29.         a--;
  30.         b--;
  31.         v[a].push_back(b);
  32.         v[b].push_back(a);
  33.      }
  34.      dfs(0, 0, 1.0, 0);
  35.    
  36.     printf("%.6lf\n", ans);
  37.     return 0;
  38. }
  39.  
  40.  
  41.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement