| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 735207 | vjudge1 | 구슬과 끈 (APIO14_beads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}