이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using t_road = pair<int, int>;
using t_roads = vector<t_road>;
using t_graph = vector<t_roads>;
using ipair = t_road;
int N;
t_graph tree;
void update (ipair &fmx_and_smx, int value) {
if (fmx_and_smx.first <= value) {
fmx_and_smx.second = fmx_and_smx.first;
fmx_and_smx.first = value;
} else if (fmx_and_smx.second <= value)
fmx_and_smx.second = value;
}
ipair dfs (int node, int parent, int upper_road) {
ipair fmx_and_smx = { - 1e9, - 1e9 };
int sum_of = 0;
for (const auto &road : tree[node]) if (road.first != parent) {
ipair result = dfs(road.first, node, road.second);
int maxv = max(result.first, result.second);
int othv = result.first;
int delta = othv - maxv + road.second;
sum_of += maxv;
update(fmx_and_smx, delta);
}
int r0 = sum_of + max(0, fmx_and_smx.first + fmx_and_smx.second);
int r1 = sum_of + max(0, fmx_and_smx.first + upper_road);
return { max(r0, 0), max(r1, 0) };
}
int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N;
tree.resize(N);
for (int iR = 1; iR < N; iR ++) {
int a, b, c;
cin >> a >> b >> c;
a --; b --;
tree[a].push_back({ b, c });
tree[b].push_back({ a, c });
}
pair<int, int> result = dfs(0, -1, 0);
cout << result.first << endl;
}
# | 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... |