Advertisement
Malinovsky239

Untitled

Jul 2nd, 2011
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. #pragma comment(linker, "/STACK:100000000")
  6.  
  7. #define N int(1e5)
  8. #define pb push_back
  9.  
  10. using namespace std;
  11.  
  12. typedef long long LL;
  13.  
  14. vector<int> graph[N], cost[N];
  15. bool was[N];
  16. LL ans = 0;
  17. int n;
  18.  
  19. int dfs(int v, int Cost)
  20. {
  21.     int res = 1;
  22.     was[v] = true;
  23.     for (int i = 0; i < graph[v].size(); i++)
  24.     {
  25.         int u = graph[v][i];
  26.         if (!was[u])
  27.         {
  28.             res += dfs(u, cost[v][i]);
  29.         }
  30.     }
  31.     LL add = Cost;
  32.     add *= res * (n - res);
  33.     ans += add;
  34.     return res;
  35. }
  36.  
  37. int main()
  38. {  
  39.     cin >> n;
  40.     for (int i = 1; i < n; i++)
  41.     {
  42.         int a, b, c;
  43.         cin >> a >> b >> c;
  44.         graph[a].pb(b);
  45.         graph[b].pb(a);
  46.         cost[a].pb(c);
  47.         cost[b].pb(c);
  48.     }
  49.  
  50.     dfs(1, 0);
  51.  
  52.     cout.precision(4);
  53.     cout << fixed << double(ans) / ( LL(n) * (n - 1) / 2);
  54.  
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement