이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
vector<pair<int, ll>> adj[N];
ll dp[2][N];
void dfs(int v, int p = 0) {
if (adj[v].size() == 1 && adj[v][0].first == p) {
dp[0][v] = 0;
dp[1][v] = -4e9;
}
ll mx = -4e9, mx2 = -4e9;
ll sum = 0;
for (auto& [x, w] : adj[v]) {
if (x == p) continue;
dfs(x, v);
ll val = max(dp[0][x], dp[1][x] + w);
sum += val;
ll val2 = dp[0][x] + w - val;
if (val2 > mx) {
mx2 = mx;
mx = val2;
}
else if (val2 > mx2) {
mx2 = val2;
}
}
dp[1][v] = sum + mx;
dp[0][v] = max(sum, sum + mx + mx2);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
// freopen("stdin", "r", stdin);
// freopen("stdout", "w", stdout);
int n;
cin >> n;
for (int i = 1;i < n;i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({ v,w });
adj[v].push_back({ u,w });
}
dfs(1);
cout << max(0ll, dp[0][1]);
return 0;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |