Submission #1176645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176645		12345678	Beads and wires (APIO14_beads)	C++17	100 / 100	71 ms	28088 KiB

beads

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, u, v, w, dp[nx][2][2];
vector<pair<ll, ll>> d[nx];

void dfs(int u, int p, ll pw)
{
    ll sm=0, mx=-1e18;
    pair<ll, ll> mx1={-1e18, 0}, smx1={-1e18, 0}, mx2={-1e18, 0}, smx2={-1e18, 0};
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        dfs(v, u, w);
        int cur=max(dp[v][1][0], dp[v][0][0]);
        sm+=cur;
        mx=max(mx, max(dp[v][0][1], dp[v][1][1])-cur);
        int vl1=max(dp[v][0][0], dp[v][0][1])-cur+w;
        if (vl1>mx1.first) swap(mx1, smx1), mx1={vl1, v};
        else if (vl1>smx1.first) smx1={vl1, v};
        int vl2=dp[v][0][0]-cur+w;
        if (vl2>mx2.first) swap(mx2, smx2), mx2={vl2, v};
        else if (vl2>smx2.first) smx2={vl2, v};
    }
    dp[u][0][0]=sm;
    dp[u][0][1]=max(sm, sm+mx);
    if (mx1.second==mx2.second) dp[u][0][1]=max(dp[u][0][1], sm+max(mx1.first+smx2.first, smx1.first+mx2.first));
    else dp[u][0][1]=max(dp[u][0][1], sm+mx1.first+mx2.first);
    dp[u][1][0]=max(sm, sm+mx2.first+pw);
    dp[u][1][1]=max(sm, sm+mx1.first+pw);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    dfs(1, 1, 0);
    cout<<max({dp[1][0][0], dp[1][0][1]});
}

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