Submission #734278

#	Time	Username	Problem	Language	Result	Execution time	Memory
734278		Alihan_8	Beads and wires (APIO14_beads)	C++17	0 / 100	0 ms	212 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});
    }
    vector <int> depth(n);
    int it = -1;
    function <void(int,int)> f = [&](int x, int par){
        if ( par == -1 ){
            depth[x] = 0; it = x;
        }
        else if ( depth[it] < depth[x] ){
            it = x;
        }
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            depth[to] = depth[x] + w;
            f(to, x);
        }
    };
    f(0, -1);
    int L = it;
    f(L, -1);
    int R = it;
    const int inf = 1e18 + 1;
    vector <array<int,2>> dp(n);
    function <void(int,int,int)> dfs = [&](int x, int par, int prev){
        int cnt = 0, l = -inf, r = -inf;
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            dfs(to, x, w);
            cnt += dp[to][1];
            int v = dp[to][0] - dp[to][1] + w;
            if ( l <= v ){
                r = l; l = v;
            }
            else chmax(r, v);
        }
        dp[x][0] = cnt;
        if ( par != -1 ){
            dp[x][1] = l + cnt + prev;
        }
        else dp[x][1] = l + cnt + r;
        chmax(dp[x][1], dp[x][0]);
    };
    int Mx = 0;
    dfs(L, -1, 0);
    Mx = dp[L][1];
    dfs(R, -1, 0);
    chmax(Mx, dp[R][1]);
    cout << Mx;

    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
*/

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