fork(1) download
copy 
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30.  
  31. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  32. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  33. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  34.  
  35. const int MN = 10111;
  36.  
  37. vector< pair<int,int > > ke[MN];
  38. int sz[MN], father[MN];
  39.  
  40. void dfs(int u, int fu = -1) {
  41.     father[u] = fu;
  42.     sz[u] = 1;
  43.     REP(i,ke[u].size()) {
  44.         int v = ke[u][i].first;
  45.         if (v == fu) continue;
  46.  
  47.         dfs(v, u);
  48.         sz[u] += sz[v];
  49.     }
  50. }
  51.  
  52. int main() {
  53.     ios :: sync_with_stdio(false); cin.tie(NULL);
  54.     cout << (fixed) << setprecision(6);
  55.     int test; cin >> test;
  56.     while (test--) {
  57.         int n;
  58.         cin >> n;
  59.         FOR(i,1,n) ke[i].clear();
  60.         FOR(i,2,n) {
  61.             int u, v, c; cin >> u >> v >> c;
  62.             ++u; ++v;
  63.             ke[u].push_back(make_pair(v, c));
  64.             ke[v].push_back(make_pair(u, c));
  65.         }
  66.         dfs(1);
  67.  
  68.         long long sum = 0;
  69.         FOR(u,1,n)
  70.             REP(i,ke[u].size()) {
  71.                 int v = ke[u][i].first;
  72.                 if (u == father[v]) {
  73.                     sum += ke[u][i].second * (long long) sz[v] * (n - sz[v]);
  74.                 }
  75.             }
  76.         cout << (fixed) << setprecision(9) << sum / (n * (long long) (n-1) / (double) 2) << endl;
  77.     }
  78.     return 0;
  79. }
  80.  
  81.  
Success #stdin #stdout 0s 3632KB
comments (?)
stdin
copy 
1
5
0 1 6
0 2 3
0 3 7
3 4 2
stdout
copy 
8.600000000
https://ideone.com/DLQFOJ
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!