Submission #238593

#	Time	Username	Problem	Language	Result	Execution time	Memory
238593		nvmdava	Beads and wires (APIO14_beads)	C++17	0 / 100	8 ms	5120 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 200005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;

vector<pair<int, int> > adj[N];

ll dp[N][2];

void dfs(int v, int p, int y){
    ll mx1 = -100'000'000'000, mx2 = -100'000'000'000;
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dfs(x.ff, v, x.ss);

        if(dp[x.ff][0] >= dp[x.ff][1]){
            dp[v][0] += dp[x.ff][0];
            dp[v][1] += dp[x.ff][0];
            if(x.ss >= mx1){
                mx2 = mx1;
                mx1 = x.ss;
            } else mx2 = max(mx2, 1LL * x.ss);
        } else {
            dp[v][0] += dp[x.ff][1];
            dp[v][1] += dp[x.ff][1];
            ll t = x.ss - dp[x.ff][1] + dp[x.ff][0];
            if(t >= mx1){
                mx2 = mx1;
                mx1 = t;
            } else mx2 = max(mx2, t);
        }
    }
    dp[v][0] += max(mx1 + mx2, 0LL);
    dp[v][1] += y + mx1;
    dp[v][1] = max(dp[v][1], 0LL);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;

    cin>>n;

    for(int i = 1; i < n; ++i){
        int a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    dfs(1, 0, 0);

    cout<<dp[1][0];
}

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