Submission #734423

#	Time	Username	Problem	Language	Result	Execution time	Memory
734423		Alihan_8	Beads and wires (APIO14_beads)	C++17	100 / 100	358 ms	51016 KiB

beads

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <pair<int,int>> g[n];
    for ( int i = 1; i < n; i++ ){
        int x, y, w; cin >> x >> y >> w;
        g[--x].pb({--y, w});
        g[y].pb({x, w});
    }
    const int inf = 1e18 + 1;
    vector <array<int,2>> dp(n);
    multiset <int> s[n];
    vector <int> par_w(n);
    function <void(int,int,int)> dfs = [&](int x, int par, int prev){
        int cnt = 0;
        par_w[x] = prev;
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            dfs(to, x, w);
            cnt += dp[to][1];
            s[x].insert(dp[to][0] - dp[to][1] + w);

        }
        dp[x][0] = cnt;
        if ( !s[x].empty() ){
            dp[x][1] = cnt + *s[x].rbegin() + par_w[x];
        }
        chmax(dp[x][1], dp[x][0]);
    };
    int res = 0;
    function <void(int,int)> reRoot = [&](int x, int par){
        chmax(res, dp[x][0]);
        auto erase = [&](int x, int val){
            s[x].erase(s[x].find(val));
        };
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            par_w[x] = w; par_w[to] = 0;
            erase(x, -dp[to][1] + dp[to][0] + w);
            dp[x][0] -= dp[to][1];
            dp[x][1] = dp[x][0];
            if ( !s[x].empty() ){
                chmax(dp[x][1], dp[x][0] + *s[x].rbegin() + par_w[x]);
            }
            s[to].insert(dp[x][0] + w - dp[x][1]);
            dp[to][0] += dp[x][1];
            dp[to][1] = max(dp[to][0], dp[to][0] + *s[to].rbegin() + par_w[to]);
            reRoot(to, x);
            swap(x, to);
            par_w[x] = w; par_w[to] = 0;
            erase(x, -dp[to][1] + dp[to][0] + w);
            dp[x][0] -= dp[to][1];
            dp[x][1] = dp[x][0];
            if ( !s[x].empty() ){
                chmax(dp[x][1], dp[x][0] + *s[x].rbegin() + par_w[x]);
            }
            s[to].insert(dp[x][0] + w - dp[x][1]);
            dp[to][0] += dp[x][1];
            dp[to][1] = max(dp[to][0], dp[to][0] + *s[to].rbegin() + par_w[to]);
            swap(x, to);
        }
    };
    dfs(0, -1, 0);
    reRoot(0, -1);
    cout << res;

    cout << '\n';
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:39:15: warning: unused variable 'inf' [-Wunused-variable]
   39 |     const int inf = 1e18 + 1;
      |               ^~~

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