fork download
copy 
  1. /*
  2.  *
  3.  ********************************************************************************************
  4.  * AUTHOR : Vijju123                                                                        *
  5.  * Language: C++14                                                                          *
  6.  * Purpose: -                                                                               *
  7.  * IDE used: Codechef IDE.                                                                  *
  8.  ********************************************************************************************
  9.  *
  10.  Comments will be included in practice problems if it helps ^^
  11.  */
  12.  
  13.  
  14.  
  15. #include <iostream>
  16. #include<bits/stdc++.h>
  17. using namespace std;
  18. double ans=0;
  19. void DFS(vector<int>arr[],int u, int previous,int level,double p)
  20. {
  21.  
  22.     if(arr[u].size()==1 && u!=1)
  23.     {
  24.         ans+=level*p;
  25.         return;
  26.     }
  27.     int i;
  28.     int denominator=arr[u].size()-1;
  29.     if(u==1)denominator++;
  30.     for(i=0;i<arr[u].size();i++)
  31.     {
  32.         if(arr[u][i]!=previous)
  33.             DFS(arr,arr[u][i],u,level+1,p/denominator );
  34.     }
  35.     return;
  36. }
  37. int main() {
  38. 	// your code goes here
  39. 	#ifdef JUDGE
  40.     freopen("input.txt", "rt", stdin);
  41.     freopen("output.txt", "wt", stdout);
  42.     #endif
  43. 	ios_base::sync_with_stdio(0);
  44. 	cin.tie(NULL);
  45. 	cout.tie(NULL);
  46. 	int n;
  47. 	cin>>n;
  48. 	vector<int> arr[n+1];
  49. 	int i,u,v;
  50. 	for(i=0;i<n-1;i++)
  51. 	{
  52. 	    cin>>u>>v;
  53. 	    arr[u].push_back(v);
  54. 	    arr[v].push_back(u);
  55. 	}
  56. 	//int leaf=0;
  57.  
  58. 	DFS(arr,1,0,0,1.0);
  59. 	//cout<<"leaf and depth is "<<leaf<<" "<<depth<<endl;
  60.     cout<<fixed<<setprecision(9)<<ans<<endl;
  61.  
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
1 2
1 3
1 4
stdout
copy 
1.000000000
https://ideone.com/QI2X14
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!