Submission #1162402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162402		polarity	Beads and wires (APIO14_beads)	C++20	0 / 100	0 ms	328 KiB

beads

/**
 * Solution by Charles Ran (polarity.sh)
 * Date: 2025-03-01
 * Contest: APIO 2014
 * Problem: beads
**/

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

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector<vector<pii>> adj(n);
    rep(i, 0, n - 1){
        int a, b, c; cin >> a >> b >> c;
        --a; --b;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    if (n < 3){
        cout << 0 << endl;
        return;
    }

    // { any, cannot abb }
    vector<pii> dp(n);
    vi par(n);
    function<void(int, int, int)> dfs1;
    function<void(int)> dfs2;
    dfs1 = [&](int node, int parent, int last){
        int a = 0;
        int mx = INT_MIN;

        par[node] = parent;

        for (auto &[child, cost] : adj[node]){
            if (child == parent){
                continue;
            }

            dfs1(child, node, cost);

            a += dp[child].first;
            mx = max(mx, cost + dp[child].second - dp[child].first);
        }

        if (last != -1 && mx != INT_MIN){
            mx += a;
            mx += last;
        } else {
            mx = 0;
        }

        dp[node] = {max(a, mx), a};
    };

    // when 0 is the starting bead
    dfs1(0, -1, -1);

    vector<int> brcost(n, 0);
    vector<multiset<int>> br(n);

    // precompute
    rep(i, 0, n){
        for (auto &[child, cost] : adj[i]){
            if (child == par[i]){
                continue;
            }

            br[i].insert(cost + dp[child].second - dp[child].first);
            brcost[i] += dp[child].first;
        }
    }

    int ans = dp[0].second;

    // transition to check when each node is the starting bead
    dfs2 = [&](int node){
        for (auto &[child, cost] : adj[node]){
            if (child == par[node]){
                continue;
            }

            // no connect
            int x = brcost[node] - dp[child].first;
            ans = max(ans, x + dp[child].second);

            // connect
            int adjustment = cost + dp[child].second - dp[child].first;
            br[node].erase(br[node].find(adjustment));

            int c = *prev(br[node].end());
            ans = max(ans, c + x + cost + dp[child].second);

            br[node].insert(adjustment);

            int a = max(x, c + x + cost);

            br[child].insert(cost + x - a);
            brcost[child] += a;

            dfs2(child);
        }
    };

    dfs2(0);

    cout << ans << endl;

    // previous direct dp attempt, does not work but maybe possible
    // dfs = [&](ll node, ll parent, ll last){
    //     ll a = INT_MIN, b1 = 0, b2 = 0, c = INT_MIN;
    //     ll mx1 = INT_MIN, mx2 = INT_MIN;

    //     ll x = 0;

    //     for (auto &[child, cost] : adj[node]){
    //         if (child == parent){
    //             continue;
    //         }

    //         dfs(child, node, cost);

    //         c = max(c, dp[child][0] - dp[child][2]);
    //         x += dp[child][2];

    //         if (last != -1){
    //             b1 = max(b1, last + cost + dp[child][3] - dp[child][2]);
    //             b2 = max(b2, last + cost + dp[child][4] - dp[child][2]);
    //         }

    //         ll change1 = cost + dp[child][3] - dp[child][2];
    //         ll change2 = cost + dp[child][4] - dp[child][2];

    //         a = max(a, change1 + mx2);
    //         a = max(a, change2 + mx1);

    //         mx1 = max(mx1, change1);
    //         mx2 = max(mx2, change2);
    //     }

    //     if ((parent == -1 && adj[node].size() == 1) || adj[node].size() > 1){
    //         c += x;
    //     } else {
    //         c = 0;
    //     }

    //     if ((parent == -1 && adj[node].size() == 2) || adj[node].size() > 2){
    //         a += x;
    //     } else {
    //         a = 0;
    //     }

    //     if (last != -1){
    //         b1 += x;
    //         b2 += x;
    //     } else {
    //         b1 = 0;
    //         b2 = 0;
    //     }

    //     ll b = max(b1, b2);

    //     ll ac = max(a, c);

    //     dp[node] = {max(ac, b), max(ac, b1), max(ac, b2), ac, c};
    // };
}

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

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