Submission #670254

#	Time	Username	Problem	Language	Result	Execution time	Memory
670254		fatemetmhr	Beads and wires (APIO14_beads)	C++17	100 / 100	183 ms	27768 KiB

beads

// hmmm... na dige chizi baraye goftan namoonde


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 3e5 + 10;
const int lg    = 20;
const ll  inf   = 1e18;

ll dp[2][maxn5], ans = 0, fpar[2][maxn5];
vector <pair<int, int>> adj[maxn5];

void dfs2(int v, int par){
    ll sum = 0;
    ll smx = -inf, mx = -inf;
    if(par != -1){
        sum += fpar[0][v];
        mx = max(mx, fpar[1][v] - fpar[0][v]);
    }
    for(auto [u, w] : adj[v]) if(u != par){
        sum += dp[0][u];
        ll val = dp[1][u] - dp[0][u];
        if(val >= mx)
            smx = mx, mx = val;
        else
            smx = max(smx, val);
    }
    ans = max(ans, sum);
    for(auto [u, w] : adj[v]) if(u != par){
        fpar[1][u] = w + sum - dp[0][u];
        fpar[0][u] = max(sum - dp[0][u], w + sum - dp[0][u] + (mx == dp[1][u] - dp[0][u] ? smx : mx));
        dfs2(u, v); 
    }
}


void dfs(int v, int par){
    for(auto [u, w] : adj[v]) if(u != par){
        dp[1][u] = w;
        dfs(u, v);
        dp[0][v] = max(dp[0][v] + dp[0][u], dp[1][v] + dp[1][u]);
        dp[1][v] += dp[0][u];
    }
}



int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n - 1; i ++){
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    dfs(0, -1);
    dfs2(0, -1);

    cout << ans << endl;

}

/*
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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43