func_code_string: #include <bits/stdc++.h>   using namespace std;   template <typename T, typename U>   std::istream& operator>>(std::istream& i, pair<T, U>& p) {     i >> p.first >> p.second;     return i;   }   template <typename T>   std::istream& operator>>(std::istream& i, vector<T>& t) {     for (auto& v : t) {       i >> v;     }     return i;   }   template <typename T, typename U>   std::ostream& operator<<(std::ostream& o, const pair<T, U>& p) {     o << p.first <<     << p.second;     return o;   }   template <typename T>   std::ostream& operator<<(std::ostream& o, const vector<T>& t) {     if (t.empty()) o <<   n ;     for (size_t i = 0; i < t.size(); ++i) {       o << t[i] <<    n [i == t.size() - 1];     }     return o;   }   template <typename T>   using minheap = priority_queue<T, vector<T>, greater<T>>;   template <typename T>   using maxheap = priority_queue<T, vector<T>, less<T>>;   template <typename T>   bool in(T a, T b, T c) {     return a <= b && b < c;   }   unsigned int logceil(long long first) {     return first ? 8 * sizeof(long long) - __builtin_clzll(first) : 0;   }   namespace std {   template <typename T, typename U>   struct hash<pair<T, U>> {     hash<T> t;     hash<U> u;     size_t operator()(const pair<T, U>& p) const {       return t(p.first) ^ (u(p.second) << 7);     }   };   }  // namespace std   template <typename T, typename F>   T bsh(T l, T h, const F& f) {     T r = -1, m;     while (l <= h) {       m = (l + h) / 2;       if (f(m)) {         l = m + 1;         r = m;       } else {         h = m - 1;       }     }     return r;   }   template <typename F>   double bshd(double l, double h, const F& f, double p = 1e-9) {     unsigned int r = 3 + (unsigned int)log2((h - l) / p);     while (r--) {       double m = (l + h) / 2;       if (f(m)) {         l = m;       } else {         h = m;       }     }     return (l + h) / 2;   }   template <typename T, typename F>   T bsl(T l, T h, const F& f) {     T r = -1, m;     while (l <= h) {       m = (l + h) / 2;       if (f(m)) {         h = m - 1;         r = m;       } else {         l = m + 1;       }     }     return r;   }   template <typename F>   double bsld(double l, double h, const F& f, double p = 1e-9) {     unsigned int r = 3 + (unsigned int)log2((h - l) / p);     while (r--) {       double m = (l + h) / 2;       if (f(m)) {         h = m;       } else {         l = m;       }     }     return (l + h) / 2;   }   template <typename T>   T gcd(T a, T b) {     if (a < b) swap(a, b);     return b ? gcd(b, a % b) : a;   }   template <typename T>   class vector2 : public vector<vector<T>> {    public:     vector2() {}     vector2(size_t a, size_t b, T t = T())         : vector<vector<T>>(a, vector<T>(b, t)) {}   };   template <typename T>   class vector3 : public vector<vector2<T>> {    public:     vector3() {}     vector3(size_t a, size_t b, size_t c, T t = T())         : vector<vector2<T>>(a, vector2<T>(b, c, t)) {}   };   template <typename T>   class vector4 : public vector<vector3<T>> {    public:     vector4() {}     vector4(size_t a, size_t b, size_t c, size_t d, T t = T())         : vector<vector3<T>>(a, vector3<T>(b, c, d, t)) {}   };   template <typename T>   class vector5 : public vector<vector4<T>> {    public:     vector5() {}     vector5(size_t a, size_t b, size_t c, size_t d, size_t e, T t = T())         : vector<vector4<T>>(a, vector4<T>(b, c, d, e, t)) {}   };   template <typename T>   struct Fenwick {     explicit Fenwick(unsigned int N = 0, T t = T())         : N(1u << logceil(N)), F(this->N, t), t(t) {}     explicit Fenwick(const vector<T>& A, T t = T())         : N(1u << logceil(A.size())), F(A), t(t) {       F.resize(N);       fill(F.begin() + A.size(), F.end(), t);       for (int i = 0; i < N; i++) {         int j = i + lsb(i + 1);         if (j < N) F[j] += F[i];       }     }     void add(int i, T v) {       while (i <= N) {         F[i] += v;         i += lsb(i + 1);       }     }     T sum(int i) const {       T sum(t);       while (i) {         sum += F[i - 1];         i -= lsb(i);       }       return sum;     }     T range(int i, int j) const {       j++;       T s(t);       while (j > i) {         s += F[j - 1];         j -= lsb(j);       }       while (i > j) {         s -= F[i - 1];         i -= lsb(i);       }       return s;     }     T get(int i) const { return range(i, i); }     void set(int i, T v) { add(i, v - get(i)); }     constexpr int lsb(int i) const { return i & -i; }     unsigned int N;     vector<T> F;     T t;     int max_lower(T v) {       if (F[0] >= v) return 0;       if (F[N - 1] < v) return N - 1;       int first = 0;       T a = t;       for (int s = N >> 1; s > 0; s >>= 1)         if (a + F[first + s - 1] < v) {           a += F[first + s - 1];           first += s;         }       return first;     }   };   template <typename T>   struct Fenwick2 {     explicit Fenwick2(unsigned int N = 0, T t = T())         : N(1u << logceil(N)), F(this->N, this->N, t), t(t) {}     void add(int first, int second, T v) {       while (first <= N) {         int z = second;         while (z <= N) {           F[first][z] += v;           z += lsb(z + 1);         }         first += lsb(first + 1);       }     }     T sum(int first, int second) {       T sum(t);       while (first <= N) {         int z = second;         while (z <= N) {           sum += F[first][z];           z -= lsb(z + 1);         }         first -= lsb(first + 1);       }       return sum;     }     T range(int x1, int y1, int x2, int y2) {       T ans = sum(x2, y2);       if (x1) ans -= sum(x1 - 1, y2);       if (y1) ans -= sum(x2, y1 - 1);       if (x1 && y1) ans += sum(x1 - 1, y1 - 1);       return ans;     }     constexpr int lsb(int i) const { return i & -i; }     unsigned int N;     vector2<T> F;     T t;   };   class FNiyazAndSmallDegrees {    public:     int N, X;     vector<map<int, int>> E;     vector<map<int, int>> ZZ;     vector<int> D, V;     vector<Fenwick<int>> CNT;     vector<Fenwick<long long>> SUM;     void add(int hiDeg, int idInFenwick, int cost) {       CNT[hiDeg].add(idInFenwick, 1);       SUM[hiDeg].add(idInFenwick, cost);     }     long long sumLowest(int hiDeg, int cnt) {       if (cnt <= 0) return 0LL;       int id = CNT[hiDeg].max_lower(cnt);       if (id == CNT[hiDeg].N - 1) return 1e12;       return SUM[hiDeg].sum(id + 1);     }     pair<long long, long long> solve(int u, int p, long long parentCost) {       V[u] = X;       long long tot = 0;       vector<long long> Q;       for (std::pair<int, int> v : E[u]) {         if (v.first != p) {           auto sol = solve(v.first, u, v.second);           tot += sol.first;           Q.push_back(sol.second);         }       }       sort(Q.begin(), Q.end());       long long ans1 = 1e12, ans2 = 1e12, pref = 0;       vector<long long> sumL(Q.size() + 2);       int toRem = D[u] - X;       for (int i = 0; i <= Q.size() + 1; ++i) sumL[i] = sumLowest(u, toRem - i);       for (int i = 0; i <= Q.size(); ++i) {         ans1 = min(ans1, pref + sumL[i]);         ans2 = min(ans2, pref + sumL[i + 1]);         if (i != Q.size()) pref += Q[i];       }       return {tot + ans1, ans2 - ans1 + parentCost};     }     void solve(istream& cin, ostream& cout) {       cin >> N;       E.resize(N);       D.resize(N);       ZZ.resize(N);       for (int i = 0; i < N - 1; ++i) {         int a, b, c;         cin >> a >> b >> c;         --a;         --b;         E[a][b] = c;         E[b][a] = c;       }       map<int, vector<int>> ByDeg;       for (int i = 0; i < N; ++i) {         D[i] = E[i].size();         ByDeg[D[i]].push_back(i);         vector<std::pair<int, int>> ByCost;         for (std::pair<int, int> e : E[i]) ByCost.emplace_back(e.second, e.first);         sort(ByCost.begin(), ByCost.end());         for (int j = 0; j < D[i]; ++j) ZZ[i][ByCost[j].second] = j;         CNT.emplace_back(D[i], 0);         SUM.emplace_back(D[i], 0LL);       }       V.assign(N, -1);       vector<long long> Cost(N, 0LL);       for (X = 0; X < N; ++X) {         for (int v : ByDeg[X]) {           for (std::pair<int, int> q : E[v]) {             add(q.first, ZZ[q.first][v], q.second);             E[q.first].erase(v);           }         }         ByDeg.erase(X);         for (auto& bd : ByDeg) {           for (int v : bd.second) {             if (V[v] != X) {               auto ans = solve(v, -1, 1e12);               Cost[X] += ans.first + min(0LL, ans.second);             }           }         }       }       cout << Cost;     }   };   int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);     FNiyazAndSmallDegrees solver;     std::istream& in(std::cin);     std::ostream& out(std::cout);     solver.solve(in, out);     return 0;   }   