제출 #1129398

#제출 시각아이디문제언어결과실행 시간메모리
1129398Hamed_Ghaffari구슬과 끈 (APIO14_beads)C++20
0 / 100
4 ms4936 KiB
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a, b) (a = max(a,b))
#define mins(a, b) (a = min(a,b))
#define Mp make_pair
#define mid ((l+r)>>1)

const int MXN = 2e5+1;
const int INF = 1e9;

int n;
ll dp00[MXN], dp01[MXN], dp10[MXN], dp11[MXN];
vector<pii> g[MXN];

void dfs(int v, int p=0) {
    for(auto [u, w] : g[v])
        if(u != p)
            dfs(u, v);
    
    dp01[v] = dp10[v] = dp11[v] = -INF;
    ll mx1=-INF, mx2=-INF;
    for(auto [u, w] : g[v])
        if(u!=p) {
            ll val = max({dp00[u], dp11[u], dp10[u]+w});
            dp00[v] += val;
            val = max(dp00[u],dp11[u])+w-val;
            if(val>=mx1) swap(val, mx1);
            if(val>=mx2) swap(val, mx2);
        }
    for(auto [u, w] : g[v])
        if(u!=p) {
            ll val = max({dp00[u], dp11[u], dp10[u]+w});
            maxs(dp11[v], dp00[v]-val+dp01[u]+w);
            maxs(dp01[v], dp00[v]-val+max(dp00[u], dp11[u])+w);
            maxs(dp10[v], dp00[v]-val+dp00[u]+w);
            maxs(dp11[v], dp00[v]-val+w
            + (max(dp00[u], dp11[u])+w-val==mx1 ? mx2 : mx1));
        }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    cin >> n;
    for(int i=0,u,v,w; i<n-1; i++) {
        cin >> u >> v >> w;
        g[u].pb(Mp(v,w));
        g[v].pb(Mp(u,w));
    }

    dfs(1);
    cout << max(dp00[1], dp11[1]) << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...