Submission #235856

#	Time	Username	Problem	Language	Result	Execution time	Memory
235856		balbit	Beads and wires (APIO14_beads)	C++14	100 / 100	243 ms	37220 KiB

beads

#include <bits/stdc++.h>
using namespace std;


#define ll long long

#define int ll

#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
const int maxn = 2e5+5;
vector<pii> g[maxn];
ll dp[maxn][2][2];

void dfs(int v, int p, ll w) {
    vector<pair<ll, ll> > mo0, mo1;
    ll sg0 = 0;
    ll hmm = 0;
    for (pii u : g[v]) {
        if (u.f != p) {
            dfs(u.f,v,u.s);
            mo0.pb({dp[u.f][0][0] - dp[u.f][1][0] + u.s, u.f});
            mo1.pb({dp[u.f][0][1] - dp[u.f][1][0] + u.s, u.f});
            hmm = max(hmm, dp[u.f][1][1] - dp[u.f][1][0]);
            sg0 += dp[u.f][1][0]      ;
//            sg1 += dp[u.f][1][1]      ;
        }
    }
    sort(ALL(mo0), greater<pair<ll, ll> >());
    sort(ALL(mo1), greater<pair<ll, ll>>());
    dp[v][0][0] = sg0;
    dp[v][0][1] = sg0 + hmm;
    if (SZ(mo0) >= 2) {
        // dp[v][0][1]
        if (mo0[0].s != mo1[0].s)
            dp[v][0][1] = max(dp[v][0][1], sg0 + mo0[0].f + mo1[0].f);
        else
            dp[v][0][1] = max(dp[v][0][1], sg0 + max(mo0[0].f + mo1[1].f, mo1[0].f + mo0[1].f));
    }
    dp[v][1][0] = dp[v][0][0];
    dp[v][1][1] = dp[v][0][1];
    if (SZ(mo0) >= 1) {
        dp[v][1][0] = max(dp[v][1][0], sg0 + mo0[0].f + w);
        dp[v][1][1] = max(dp[v][1][1], sg0 + mo1[0].f + w);
        dp[v][1][1] = max(dp[v][1][1], dp[v][1][0]);
    }
}

signed main(){
    IOS();

    int n; cin>>n;
//    assert(n == 5 || n==10);
//    vector<pair<pii, int> > v;
    for (int i = 0; i<n-1; ++i) {
        int a,b,w; cin>>a>>b>>w;
//        if (n == 5 ) assert(a == 1);
        --a;--b;
//        v.pb({{a,b},w});
        g[a].pb({b,w});g[b].pb({a,w});
    }
//    cout<<re<<endl;
    dfs(0,-1,0);
    cout<<dp[0][0][1]<<endl;

}
/*
6
1 2 10
1 3 10
1 4 1
4 5 10
4 6 10
*/

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