Submission #754002

#	Time	Username	Problem	Language	Result	Execution time	Memory
754002		thinknoexit	Beads and wires (APIO14_beads)	C++17	0 / 100	3 ms	5032 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) {
    if (adj[v].size() == 1 && adj[v][0].first == p) {
        dp[0][v] = 0;
        dp[1][v] = -2e9;
    }
    ll mx = -2e9, mx2 = -2e9;
    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;
        ll val2 = dp[0][x] + w - val;
        if (val2 > mx) {
            mx2 = mx;
            mx = val2;
        }
        else if (val2 > mx2) {
            mx2 = val2;
        }
    }
    dp[1][v] = sum + mx;
    dp[0][v] = max(sum, sum + mx + mx2);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // freopen("stdin", "r", stdin);
    // freopen("stdout", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1;i < n;i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({ v,w });
        adj[v].push_back({ u,w });
    }
    dfs(1);
    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