Salvens

D

Jul 31st, 2023 (edited)
824
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <array>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10. #pragma comment(linker,"/STACK:1000000000,1000000000")
  11.  
  12. const long long INF = 1e18 + 7;
  13. const int MAXN = 5e4 + 100;
  14. const int N = 1e5 + 10;
  15. const int MOD = 1e9 + 7;
  16.  
  17. vector<int> dp;
  18. vector<int> used;
  19. vector<vector<pair<int, int>>> g;
  20.  
  21. int n, sum = 0;
  22.  
  23. void dfs(int v) {
  24.     used[v] = true;
  25.     for (auto [to, w]: g[v]) {
  26.         if (!used[to]) {
  27.             dfs(to);
  28.             dp[v] += dp[to];
  29.             sum += w * dp[to] * (n - dp[to]);
  30.         }
  31.     }
  32.     ++dp[v];
  33. }
  34.  
  35. signed main() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(nullptr);
  38.     cout.tie(nullptr);
  39.     cin >> n;
  40.     dp.resize(n, 0);
  41.     used.resize(n, 0);
  42.     g.resize(n);
  43.     if (n == 1) {
  44.         cout << 0 << '\n';
  45.         return 0;
  46.     }
  47.     for (int i = 0; i < n - 1; ++i) {
  48.         int u, v, w;
  49.         cin >> u >> v >> w;
  50.         --u, --v;
  51.         g[u].emplace_back(v, w);
  52.         g[v].emplace_back(u, w);
  53.     }
  54.     dfs(0);
  55.     sum *= 2;
  56.     cout << setprecision(10) << fixed;
  57.     cout << double(sum) / double(n * (n - 1)) << '\n';
  58. }
Advertisement
Add Comment
Please, Sign In to add comment