Submission #754040

#	Time	Username	Problem	Language	Result	Execution time	Memory
754040		thinknoexit	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	5024 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];
bool vis[N];
void dfs(int v, int p = 0) {
    ll mx = -4e10, mx2 = -4e10;
    ll sum = 0;
    vis[v] = 1;
    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);
    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 });
    }
    ll ans = 0;
    for (int i = 1;i <= n;i++) {
        if (vis[i]) continue;
        dfs(i);
        ans += dp[0][i];
    }
    cout << ans;
    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