제출 #238696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238696		nvmdava	구슬과 끈 (APIO14_beads)	C++17	0 / 100	7 ms	4992 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 200005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;

vector<pair<int, int> > adj[N];

ll dp[N][2];

void dfs(int v, int p, int y){
    ll mx1 = -1'000'000'000'000, mx2 = -1'000'000'000'000;

    ll ans = 0;

    for(auto& x : adj[v]){
        if(x.ff == p) continue;
        dfs(x.ff, v, x.ss);

        ans += dp[x.ff][1];

        ll t = x.ss - (dp[x.ff][1] - dp[x.ff][0]);

        if(t > mx1){
            mx2 = mx1;
            mx1 = t;
        } else mx2 = max(mx2, t);
    }

    cout<<v<<' '<<ans<<'\n';

    dp[v][0] = ans + max(0LL, mx1 + mx2);
    dp[v][1] = max(dp[v][0], ans + y + mx1);
}

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

    int n;

    cin>>n;

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

    dfs(1, 0, 0);
    cout<<dp[1][0];
}

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