如题。
#include <bits/stdc++.h> using namespace std; #define fast_io ios::sync_with_stdio(0), cin.tie(nullptr) #define endl '\n' #define int long long #define ar array<int, 2> #define arr array<int, 3> int T, n, m, k, inf = 1e18, mod = 1e9 + 7; const int N = 3e5 + 50; vector<ar> mp[N]; ar dfs(int u, int p) { int mx = 0; int l = 0; for (auto [v, t] : mp[u]) { if (v == p) continue; auto [x, y] = dfs(v, u); mx = max(x + t - y, mx); l += y; } return {l, max(l, l + mx)}; }; signed main() { fast_io; #ifdef DEBUG freopen("../1.in", "r", stdin); #endif cin >> n; for (int i = 1; i < n; ++i) { int x, y, z; cin >> x >> y >> z; mp[x].push_back({y, z}); mp[y].push_back({x, z}); } // 为什么从一个入度为0 的边开始走 反而不行??? // for (int i = 1; i <= n; ++i) // if (mp[i].size() == 1) // { // dfs(i, 0); // } auto a = dfs(1, 0); cout << max(a[0], a[1]); }; //场景: //量级: //搞:
全部评论
(1) 回帖