Submission #240886

#	Time	Username	Problem	Language	Result	Execution time	Memory
240886		nvmdava	Beads and wires (APIO14_beads)	C++17	100 / 100	264 ms	25532 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 ans = 0;

ll dp[N][2][2];

void dfs1(int v, int p = 0, int d = 0){
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dfs1(x.ff, v, x.ss);
    }
    ll mx = 0;
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dp[v][0][0] += dp[x.ff][0][1];
        mx = max(mx, d + dp[x.ff][0][0] + x.ss - dp[x.ff][0][1]);
    }
    if(p == 0) mx = 0;
    dp[v][0][1] = dp[v][0][0] + mx;
    ans = max(ans, dp[v][0][1]);
}

void dfs2(int v, int p = 0, ll d = 0){
    ll t = dp[v][1][1];

    ll mx1 = (p == 0 ? -99999999999 : d + dp[v][1][0] - dp[v][1][1]), mx2 = -9999999999999;
    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        t += dp[x.ff][0][1];
        ll w = x.ss + dp[x.ff][0][0] - dp[x.ff][0][1];
        if(w > mx1){
            mx2 = mx1;
            mx1 = w;
        } else mx2 = max(mx2, w);
    }

    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dp[x.ff][1][0] = t - dp[x.ff][0][1];
        ll w = x.ss + dp[x.ff][0][0] - dp[x.ff][0][1];
        dp[x.ff][1][1] = dp[x.ff][1][0] + max(0LL, x.ss + (w == mx1 ? mx2 : mx1));
        ans = max(ans, dp[x.ff][1][1]);
        dfs2(x.ff, v, x.ss);
    }
}

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

    int n;
    cin>>n;
    for(int x, y, z, i = 1; i < n; ++i){
        cin>>x>>y>>z;
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }
    dfs1(1);
    dfs2(1);

    cout<<ans;

}

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