Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <array>
- #include <set>
- using namespace std;
- #define int long long
- #pragma comment(linker,"/STACK:1000000000,1000000000")
- const long long INF = 1e18 + 7;
- const int MAXN = 5e4 + 100;
- const int N = 1e5 + 10;
- const int MOD = 1e9 + 7;
- vector<int> dp;
- vector<int> used;
- vector<vector<pair<int, int>>> g;
- int n, sum = 0;
- void dfs(int v) {
- used[v] = true;
- for (auto [to, w]: g[v]) {
- if (!used[to]) {
- dfs(to);
- dp[v] += dp[to];
- sum += w * dp[to] * (n - dp[to]);
- }
- }
- ++dp[v];
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cin >> n;
- dp.resize(n, 0);
- used.resize(n, 0);
- g.resize(n);
- if (n == 1) {
- cout << 0 << '\n';
- return 0;
- }
- for (int i = 0; i < n - 1; ++i) {
- int u, v, w;
- cin >> u >> v >> w;
- --u, --v;
- g[u].emplace_back(v, w);
- g[v].emplace_back(u, w);
- }
- dfs(0);
- sum *= 2;
- cout << setprecision(10) << fixed;
- cout << double(sum) / double(n * (n - 1)) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment