Submission #924984

#	Time	Username	Problem	Language	Result	Execution time	Memory
924984		thinknoexit	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	10588 KiB

beads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
const ll INF = 2e9;
vector<pair<int, int>> adj[N];
ll dp[5][N];
void dfs(int v, int p = -1) {
    ll mx0 = 0, mx2 = -INF, mx3 = -INF;
    ll mx[3] = { -INF, -INF, -INF };
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        ll val = max(dp[1][x], dp[2][x] + w);
        // 0
        dp[0][v] += val;
        mx0 = max(mx0, max(dp[0][x], dp[3][x] + w) - val);
        // 1
        dp[1][v] += val;
        // 2
        dp[2][v] += val;
        mx2 = max(mx2, dp[1][x] + w - val);
        // 3
        dp[3][v] += val;
        mx3 = max(mx3, dp[4][x] + w - val);
        // 4
        dp[4][v] += val;
        mx[1] = max(mx[1], dp[1][x] + w - val);
        mx[2] = max(mx[2], dp[4][x] + w - val);
        if (mx[0] < mx[1]) swap(mx[0], mx[1]);
    }
    dp[0][v] += mx0;
    dp[2][v] += mx2;
    dp[3][v] += mx3;
    dp[4][v] += max(mx[0] + mx[1], mx[0] + mx[2]);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i < n;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    dfs(1);
    cout << max(dp[0][1], dp[4][1]);
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43