题目描述：

给定一个带权树，树上任意两点间的路径权值 \(d\left(x,y\right)\) 定义为 \(x,y\) 这两个点之间路径上的最小值，树上任意一点x的权值定义为这个点到树上其他所有点的路径权值和，即 \(\sum d\left(x,i\right)\)，现求树上每一个点的路径权值和。

Input Format

首先输入一个整数 \(n\left(1 \leq n \leq 10^5 \right)\) ，表示树的点的个数。　
接下来 \(n−1\) 行，每行三个整数 \(x,y,s\left(1\leq x,y\leq n,1\leq s \leq 1000\right)\) ，表示编号为 \(x\) 的节点和编号为 \(y\) 的节点之间存在一条权值为 \(s\) 的边，树上每个点的编号为 \(1\sim n\)

Output Format

n行，每行输出每个节点对应的路径权值和

Sample Input

    4
    1 2 2
    2 4 1
    2 3 1

Sample Output

    4
    4
    3
    3

思路：

    #include <bits/stdc++.h>

    using i64 = long long;

    #define rep(i,a,b) for (int i = a; i < b; i++)
    #define per(i,a,b) for (int i = a; i >= b; i--)
    #define SZ(s) int(s.size())
    #define all(v) v.begin(), v.end()

    template <typename T>
    struct Fenwick {
        const int n;
        std::vector<T> tr;
        Fenwick(int n) : n(n), tr(n + 1) {}

        void add(int x, T v) {
            for (int i = x; i <= n; i += i & -i) 
                tr[i] += v;
        }

        T sum(int x) {
            T ans = 0;
            for (int i = x; i; i-=i&-i) ans += tr[i];
            return ans;
        }
        
        T rangeSum(int l, int r) {return sum(r) - sum(l);}
        
        int query(T s) { // 查询1~pos的和小于等于s
            int pos = 0;
            for (int j = 18; j >= 0; j -- ) 
                if ((pos + (1ll << j) < n) && tr[pos + (1ll << j)] <= s) 
                    pos = (pos + (1 << j)), s -= tr[pos];
            return pos;
        }
    };

    struct DSU {  
        std::vector<int> f, siz;  
        DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }  
    
        int leader(int x) {  
            while (x != f[x]) x = f[x] = f[f[x]];  
            return x;  
        }  
    
        bool same(int x, int y) { return leader(x) == leader(y); }  
    
        bool merge(int x, int y) {  
            x = leader(x);  
            y = leader(y);  
            if (x == y) return false;  
            siz[x] += siz[y];  
            f[y] = x;
            return true;  
        }  
        
        int size(int x) { return siz[leader(x)]; }  
    };

    signed main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n; std::cin >> n;
        int now = n;
        std::vector<std::array<int, 3>> edge;
        std::vector<std::vector<int>> adj(n * 2);
        std::vector<int> val(n * 2);
        for (int i = 1; i < n; i++) {
            int u, v, w;
            std::cin >> u >> v >> w;
            edge.push_back({w, u, v});
        }

        DSU uf(n * 2 + 1);
        std::sort(edge.begin(), edge.end(), std::greater<std::array<int, 3>>());

        for (auto& [w, u, v] : edge) {
            int fu = uf.leader(u), fv = uf.leader(v);
            val[++now] = w;
            uf.f[fu] = uf.f[fv] = now;
            adj[now].push_back(fu), adj[now].push_back(fv);
        }

        Fenwick<int> bit(now);

        std::vector<int> siz(now + 1);
        std::vector<std::array<int, 2>> seg(now + 1);
        int idx = 0;

        std::function<void(int)> dfs = [&](int u) -> void {
            siz[u] = (u <= n);
            seg[u][0] = ++idx;
            for (auto& v : adj[u]) {
                dfs(v);
                siz[u] += siz[v];
            }
            seg[u][1] = idx;
        };

        dfs(now);

        auto change = [&](int x, int v) -> void {
            bit.add(seg[x][0], v);
            bit.add(seg[x][1] + 1, -v);
        };

        for (int i = n + 1; i <= now; i++) {
            change(adj[i][0], siz[adj[i][1]] * val[i]);
            change(adj[i][1], siz[adj[i][0]] * val[i]);
        }

        for (int i = 1; i <= n; i++) std::cout << bit.sum(seg[i][0]) << "\n";
        return 0 ^ 0;
    }