Submission #754344

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

beads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
vector<pair<int, ll>> adj[N];
ll dp[2][N];
void dfs(int v, int p = 0) {
    ll mx = -4e10, mx2 = -4e10;
    ll sum = 0;
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        ll val = max(dp[0][x], dp[1][x] + w);
        sum += val;
        mx2 = max(mx2, dp[0][x] + w - val);
        if (mx < mx2) swap(mx, mx2);
    }
    dp[1][v] = sum + mx;
    dp[0][v] = max(sum, sum + mx + mx2);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    ll s = 0;
    for (int i = 1;i < n;i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        s += w;
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    dfs(1);
    while (dp[0][1] > s) {
        cout << dp[0][1] << '\n';
    }
    cout << dp[0][1];
    return 0;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

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