#include "roads.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i = (a); i <= (b); i++) #define repa(i,a,b) for (int i = (a); i >= (b); i--) #define lli long long int #define debugsl(a) cout << #a << " = " << a << ", " #define debug(a) cout << #a << " = " << a << endl #define MAX 100000 #define des first #define w second lli sol[MAX+2]; vector< pair<lli,lli> > hijos[MAX+2]; lli n,a,b,c; set<lli> dfs(lli pos, lli padre) { set<lli> usados; set<lli>::iterator x; usados.insert(n+1); for (auto h : hijos[pos]) { if (h.des == padre) continue; set<lli> otros = dfs(h.des,pos); rep(y,1,n) { x = otros.lower_bound(y); if ((*x) == y) continue; x = usados.lower_bound(y); if ((*x) != y) { sol[y]++; usados.insert(y); break; } } } return usados; } std::vector <long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vector<long long> res (N, 0); n = N; //asigna hijos rep(i,0,n-2) { a = U[i]+1; b = V[i]+1; c = W[i]; hijos[a].push_back({b,c}); hijos[b].push_back({a,c}); } res[0] = n-1; set<lli> xx = dfs(1,0); rep(i,1,n-1) res[i] = res[i-1] - sol[i]; return res; }