Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n;
- const int max_=100000;
- double ans=0;
- vector<int>v[max_];
- void dfs(int at, int parent, double probabilty, int d){
- int b=0;
- for(int i:v[at]){
- if(i!=parent){
- b++;
- }
- }
- for(int i:v[at]){
- if(i!=parent){
- dfs(i, at, probabilty/b, d+1);
- }
- }
- if(b==0){
- ans+=probabilty*d;
- }
- }
- int main()
- {
- cin>>n;
- for(int i=0; i<n-1; i++){
- int a,b;
- cin>>a>>b;
- a--;
- b--;
- v[a].push_back(b);
- v[b].push_back(a);
- }
- dfs(0, 0, 1.0, 0);
- printf("%.6lf\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement