Advertisement
lmarioza

c

Aug 12th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define INF 0x3f3f3f3f
  7. #define LINF 0x3f3f3f3f3f3f3f3fLL
  8.  
  9. using namespace std;
  10. typedef long long ll;
  11. typedef vector<int> vi;
  12. typedef set<int> si;
  13. typedef pair<int,int> ii;
  14. typedef vector<ii> vii;
  15. typedef map<string,int> msi;
  16. typedef map<int,int> mi;
  17.  
  18. vector<int> grafo[100010];
  19. int vis[100010];
  20. vector<int> peso;
  21. int x;
  22.  
  23. void dfs(int pai){
  24. x++;
  25. int ultimo =true;
  26. for(int i =0;i<grafo[pai].size();i++){
  27. if(!vis[grafo[pai][i]]){
  28. ultimo = false;
  29. vis[grafo[pai][i]] =1;
  30. dfs(grafo[pai][i]);
  31. }
  32. }
  33. if(ultimo){
  34. peso.pb(x);
  35. }
  36. x--;
  37. }
  38.  
  39. int main(){
  40. int n;
  41. scanf("%d",&n);
  42. for(int i=1;i<n;i++){
  43. int a,b;
  44. scanf("%d %d",&a,&b);
  45. grafo[a].pb(b);
  46. grafo[b].pb(a);
  47. }
  48. x=-1;
  49. vis[1]=1;
  50. dfs(1);
  51. double soma =0;
  52. for(vector<int>::iterator it=peso.begin();it != peso.end();it++){
  53. soma+=*it;
  54. }
  55. printf("%.14lf",soma/peso.size());
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement