// APIO 2014 Problem 3 - Beads and Wires
#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 (zenhoui-tree-dp part 1)
vector<int> par(N);
vector<pair<int, int> > dp1(N);
function<void(int, int)> solve1 = [&](int pos, int pre) {
// returns = (no mid-blue, one mid-blue)
par[pos] = pre;
int sumcost = 0, delta = -inf;
for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
if(to[i] == pre) continue;
solve1(to[i], pos);
sumcost += max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
delta = max(delta, min(dp1[to[i]].first - dp1[to[i]].second, cost[i]));
}
dp1[pos] = make_pair(sumcost, sumcost + delta);
};
solve1(0, -1);
// step #4. calculation (zenhoui-tree-dp part 2)
vector<pair<int, int> > dp2(N);
function<void(int, int)> solve2 = [&](int pos, int pre) {
int sumcost = 0, parcost = -inf;
vector<pair<int, int> > deltas;
for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
if(to[i] == pre) {
parcost = cost[i];
continue;
}
sumcost += max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
deltas.push_back(make_pair(min(dp1[to[i]].first - dp1[to[i]].second, cost[i]), i));
}
deltas.push_back(make_pair(min(dp1[pos].first - dp1[pos].second, parcost), -1));
sort(deltas.begin(), deltas.end(), greater<pair<int, int> >());
sumcost += max(dp2[pos].first, (parcost != -inf ? dp2[pos].second + parcost : -inf));
for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
if(to[i] == pre) continue;
pair<int, int> dm = make_pair(min(dp1[to[i]].first - dp1[to[i]].second, cost[i]), i);
int sc = sumcost - max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
dp2[to[i]] = make_pair(sc, sc + (dm != deltas[0] ? deltas[0].first : deltas[1].first));
solve2(to[i], pos);
}
};
dp2[0] = make_pair(0, -inf);
solve2(0, -1);
// step #5. calculate and print the answer
int ans = 0;
for(int i = 0; i < N; ++i) {
int sumcost = 0;
for(int j = sep[i]; j < sep[i + 1]; ++j) {
if(to[j] == par[i]) {
sumcost += max(dp2[i].first, dp2[i].second + cost[j]);
}
else {
sumcost += max(dp1[to[j]].first, dp1[to[j]].second + cost[j]);
}
}
ans = max(ans, sumcost);
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
