注意父亲节点为叶子节点的情况就行了
/********************************************************************* 程序名: 版权: Joecai 作者: Joecai 日期: 2022-04-13 23:47 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 2e5 + 10, INF = 0x3f3f3f3f; struct node { ll to; ll w; }; vector<node>g[N]; ll du[N]; ll sum[N]; void dfs1(int u, int f) { for (auto x : g[u]) { if (x.to == f) continue; dfs1(x.to, u); if (du[x.to] > 1) { sum[u] += min(x.w, sum[x.to]); } else { sum[u] += x.w; } } } void dfs(int u, int f) { for (auto x : g[u]) { if (x.to == f) continue; if (du[x.to] > 1) { sum[x.to] = sum[x.to] + min((sum[u] - min(x.w, sum[x.to])) == 0 ? x.w : (sum[u] - min(x.w, sum[x.to])), x.w); } else sum[x.to] = min(sum[u] - x.w, x.w); dfs(x.to, u); } return; } void solve() { int n; cin >> n; for (int i = 1; i <= n - 1; i++) { int x, y, w; cin >> x >> y >> w; du[x]++; du[y]++; g[x].push_back({y, w}); g[y].push_back({x, w}); } dfs1(1, 0); dfs(1, 0); for (int i = 1; i <= n; i++) { cout << sum[i] << endl; } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }