#include "roads.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const int lim = 1e5 + 5; int n; vector<int>u, v, w, g[lim]; namespace sub1{ vector<ll>solve(){ sort(w.begin(), w.end(), greater<int>()); vector<ll>ans(n); ans[n - 1] = 0; for(int i = n - 2; i > -1; i--){ ans[i] = ans[i + 1] + w[i]; } return ans; } } namespace sub2{ bool check_subtask(){ for(int i = 0; i + 1 < n; i++){ if(u[i] != i || v[i] != i + 1){ return false; } } return true; } vector<ll>solve(){ vector<ll>dp(2, 0), ndp(2); for(int i = 0; i + 1 < n; i++, swap(dp, ndp)){ ndp[0] = dp[1]; ndp[1] = min(dp[0], dp[1]) + w[i]; } vector<ll>ans(n, 0); ans[0] = accumulate(w.begin(), w.end(), 0LL); ans[1] = min(dp[0], dp[1]); return ans; } } namespace sub34{ vector<ll>solve(){ vector<ll>ans(n); ans[0] = accumulate(w.begin(), w.end(), 0LL); for(int k = 1; k < n; k++){ function<pair<ll, ll>(int, int)>dfs; dfs = [&] (int s, int p){ vector<pair<ll, ll>>child; for(int& i : g[s]){ int d = u[i] ^ v[i] ^ s; if(d != p){ pair<ll, ll>dv = dfs(d, s); child.push_back(make_pair(dv.first, min(dv.first, dv.second) + w[i])); } } pair<ll, ll>ans = make_pair(0, 0); ll sum = 0; int need = int(g[s].size()) - k; vector<ll>dif; for(auto& [u, v] : child){ if(v <= u){ need--; sum += v; } else{ sum += u; dif.push_back(v - u); } } sort(dif.begin(), dif.end()); for(int i = 0; i < need; i++){ sum += dif[i]; } ans.first = ans.second = sum; if(need > 0){ ans.second -= dif[need - 1]; } return ans; }; ans[k] = dfs(0, -1).first; } return ans; } } namespace sub5{ vector<ll>solve(){ vector<ll>ans(n, 0); ans[0] = accumulate(w.begin(), w.end(), 0LL); vector<int>par(n), h(n), deg(n); function<void(int)>dfs; dfs = [&] (int s){ for(int& i : g[s]){ int d = u[i] ^ v[i] ^ s; if(d != par[s]){ h[d] = h[par[d] = s] + 1; dfs(d); } } }; dfs(par[0] = h[0] = 0); vector<vector<int>>vertex(n); for(int i = 0; i < n; i++){ vertex[deg[i] = g[i].size()].push_back(i); } set<pair<int, int>>s; for(int k = n - 1; k > 0; k--){ for(int& i : vertex[k]){ s.insert(make_pair(-h[i], i)); } for(auto& [foo, u] : s){ deg[u] = g[u].size(); } for(auto& [foo, u] : s){ if(deg[u] > k){ ans[k] += deg[u] - k; deg[par[u]]--; } } } return ans; } } namespace sub67{ struct Node{ int cnt, c[2]; ll s; Node(){ c[cnt = s = 0] = c[1] = -1; } }; struct Data{ vector<Node>t; Data(){ t.push_back(Node()); } void insert(int x){ for(int i = 29, r = 0; i > -1; i--){ bool N = x >> i & 1; if(t[r].c[N] == -1){ t[r].c[N] = t.size(); t.push_back(Node()); } t[r = t[r].c[N]].s += x; t[r].cnt++; } } void remove(int x){ for(int i = 29, r = 0; i > -1; i--){ t[r = t[r].c[x >> i & 1]].s -= x; t[r].cnt--; } } ll get_sum(int k){ ll ans = 0; int r = 0, val = 0; for(int i = 29; i > -1; i--){ if(t[r].c[0] == -1){ r = t[r].c[1]; val |= 1 << i; } else if(t[r].c[1] == -1){ r = t[r].c[0]; } else if(t[t[r].c[0]].cnt <= k){ ans += t[t[r].c[0]].s; k -= t[t[r].c[0]].cnt; r = t[r].c[1]; val |= 1 << i; } else{ r = t[r].c[0]; } } return ans + ll(val) * k; } int get_kth(int k){ int ans = 0; for(int i = 29, r = 0; i > -1; i--){ if(t[r].c[0] == -1){ r = t[r].c[1]; ans |= 1 << i; } else if(t[r].c[1] == -1){ r = t[r].c[0]; } else if(t[t[r].c[0]].cnt < k){ k -= t[t[r].c[0]].cnt; r = t[r].c[1]; ans |= 1 << i; } else{ r = t[r].c[0]; } } return ans; } }; Data ds[lim]; bitset<lim>vis; vector<ll>solve(){ for(int i = 0; i < n; i++){ sort(g[i].begin(), g[i].end(), [&] (int x, int y){ return g[u[x] ^ v[x] ^ i].size() > g[u[y] ^ v[y] ^ i].size(); }); for(int& j : g[i]){ ds[i].insert(w[j]); } } vector<ll>ans(n, 0); ans[0] = accumulate(w.begin(), w.end(), 0LL); vector<int>sbd(n); iota(sbd.begin(), sbd.end(), 0); sort(sbd.begin(), sbd.end(), [&] (int i, int j){ return g[i].size() > g[j].size(); }); for(int k = n - 1; k > 0; k--){ function<pair<ll, ll>(int, int)>dfs; dfs = [&] (int s, int p){ vis[s] = true; int need = int(g[s].size()) - k; pair<ll, ll>ans = make_pair(0, 0); vector<int>cache; for(int& i : g[s]){ int d = u[i] ^ v[i] ^ s; if(g[d].size() <= k){ break; } if(d != p){ ds[s].remove(w[i]); ds[d].remove(w[i]); pair<ll, ll>child = dfs(d, s); if((child.second = min(child.first, child.second) + w[i]) <= child.first){ need--; ans.first += child.second; } else{ ans.first += child.first; cache.push_back(child.second - child.first); ds[s].insert(cache.back()); } } } if(need > 0){ ans.second = (ans.first += ds[s].get_sum(need)) - ds[s].get_kth(need); } else{ ans.second = ans.first; } for(int& x : cache){ ds[s].remove(x); } for(int& i : g[s]){ int d = u[i] ^ v[i] ^ s; if(g[d].size() <= k){ break; } if(d != p){ ds[s].insert(w[i]); ds[d].insert(w[i]); } } return ans; }; for(int& i : sbd){ if(g[i].size() <= k){ break; } vis[i] = false; } for(int& i : sbd){ if(g[i].size() <= k){ break; } if(!vis[i]){ ans[k] += dfs(i, -1).first; } } } return ans; } } vector<ll>minimum_closure_costs(int N, vector<int>U, vector<int>V, vector<int>W){ n = N; swap(u, U); swap(v, V); swap(w, W); for(int i = 0; i + 1 < n; i++){ g[u[i]].push_back(i); g[v[i]].push_back(i); } if(*max_element(u.begin(), u.end()) == 0){ return sub1::solve(); } if(sub2::check_subtask()){ return sub2::solve(); } if(n <= 2000){ return sub34::solve(); } if(*max_element(w.begin(), w.end()) == 1){ return sub5::solve(); } return sub67::solve(); }