# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
735207 | vjudge1 | Beads and wires (APIO14_beads) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int main() {
int n;
cin >> n;
if (n <= 2) return cout << 0, 0;
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
vector<vector<int>> f(2, vector<int>(n, 0));
function<void(int, int)> dfs = [&](int u, int p) {
f[1][u] = -1e10;
f[0][u] = 0;
for (pair<int, int>& e : adj[u]) {
int v = e.first;
int c = e.second;
if (v == p) continue;
dfs(v, u);
f[0][u] += max(f[0][v], f[1][v] + c);
}
for (pair<int, int>& e : adj[u]) {
int v = e.first;
int c = e.second;
if (v == p) continue;
f[1][u] = max(f[1][u], f[0][u] - max(f[0][v], f[1][v] + c) + f[0][v] + c);
}
};
int res = 0;
function<void(int, int)> reroot = [&](int u, int p) {
// re-calc f[u]
int ff0 = f[0][u];
int ff1 = f[1][u];
f[0][u] = 0;
for (pair<int, int>& e : adj[u]) {
int v = e.first, c = e.second;
f[0][u] += max(f[0][v], f[1][v] + c);
}
vector<int> bestf(2, -1e10);
for (pair<int, int>& e : adj[u]) {
int v = e.first, c = e.second;
bestf.emplace_back(f[0][u] - max(f[0][v], f[1][v] + c) + f[0][v] + c);
int i = bestf.size() - 1;
while (i > 0 && bestf[i] > bestf[i - 1]) swap(bestf[i], bestf[i - 1]), i--;
bestf.pop_back();
}
f[1][u] = bestf[0];
// update result
vector<int> best;
for (pair<int, int>& e : adj[u]) {
int v = e.first, c = e.second;
best.emplace_back(f[0][v] + c - max(f[0][v], f[1][v] + c));
int i = best.size() - 1;
while (i > 0 && best[i] > best[i - 1]) swap(best[i], best[i - 1]), i--;
if (best.size() > 2) best.pop_back();
}
if (best.size() == 2) res = max(res, f[0][u] + max(0, best[0] + best[1]));
// move to the next one
for (pair<int, int>& e : adj[u]) {
int v = e.first, c = e.second;
if (v == p) continue;
int f0 = f[0][u];
f[0][u] -= max(f[0][v], f[1][v] + c);
f[1][u] = bestf[0] == (f[0][u] + f[0][v] + c) ? bestf[1] : bestf[0];
f[1][u] -= max(f[0][v], f[1][v] + c);
reroot(v, u);
f[1][u] = bestf[0];
f[0][u] = f0;
}
f[0][u] = ff0;
f[1][u] = ff1;
};
dfs(0, -1);
reroot(0, -1);
cout << res;
}