#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 2012345678;
int main() {
// step #1. read input
cin.tie(0);
ios_base::sync_with_stdio(false);
int N;
cin >> N;
vector<int> ga(N - 1), gb(N - 1), gw(N - 1);
for(int i = 0; i < N - 1; ++i) {
cin >> ga[i] >> gb[i] >> gw[i];
--ga[i], --gb[i];
}
// step #2. construct a graph
vector<int> sep(N + 1);
for(int i = 0; i < N - 1; ++i) {
++sep[ga[i] + 1];
++sep[gb[i] + 1];
}
for(int i = 0; i < N; ++i) {
sep[i + 1] += sep[i];
}
vector<int> ctr(sep);
vector<int> to(2 * N - 2), cost(2 * N - 2);
for(int i = 0; i < N - 1; ++i) {
to[ctr[ga[i]]] = gb[i]; cost[ctr[ga[i]]++] = gw[i];
to[ctr[gb[i]]] = ga[i]; cost[ctr[gb[i]]++] = gw[i];
}
// step #3. calculation
function<pair<int, int>(int, int)> solve = [&](int pos, int pre) {
// returns = (no mid-blue, one mid-blue)
int sumcost = 0, delta = -inf;
for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
if(to[i] == pre) continue;
pair<int, int> res = solve(to[i], pos);
sumcost += max(res.first, res.second + cost[i]);
delta = max(delta, min(res.second - res.first, cost[i]));
}
return make_pair(sumcost, sumcost + delta);
};
int ans = 0;
for(int i = 0; i < N; ++i) {
pair<int, int> res = solve(i, -1);
ans = max(ans, res.first);
}
// step #4. print the answer
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
