제출 #1271542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271542		bbldrizzy	구슬과 끈 (APIO14_beads)	C++20	57 / 100	1093 ms	17404 KiB

beads

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll MX = 4*1e18;
vector<vector<P>> adj;
vector<ll> dp1; // just best overall niger
vector<ll> dp2; // best given that you have a 1 extension to some child 

void calc(int nd, int pr) {
    // cout << "nd, pr: " << nd << ", " << pr << "\n";
    if (nd != pr && adj[nd].size() == 1) { // leaf nigga
        return;
    }
    vector<ll> cst(adj[nd].size());
    int idx = 0;
    for (auto c: adj[nd]) {
        if (c.f != pr) {
            int mx = 0;
            // cout << "c.f, c.s: " << c.f << ", " << c.s << "\n";
            // cout << "adj[c.f].size, c.s+dp1[c.f]: " << adj[c.f].size() << ", " << c.s+dp1[c.f] << "\n";
            mx = max((adj[c.f].size() > 1 ? c.s+dp1[c.f] : 0), dp2[c.f]);
            // cout << "mx: " << mx << "\n";
            cst[idx] = mx;
            idx++;
            dp2[nd] += mx;
        }
    }
    ll ovr = dp2[nd];
    ll lhs = 0;
    idx = 0;
    for (auto c: adj[nd]) {
        if (c.f != pr) {
            ovr -= cst[idx];
            dp1[nd] = max(dp1[nd], lhs+ovr+dp2[c.f]+c.s);
            lhs += cst[idx];
            idx++;
        }
    }
}

ll mx = 0;

void dfs(int nd, int pr) {
    for (auto c: adj[nd]) {
        if (c.f != pr) {
            dfs(c.f, nd);    
        }
    }
    calc(nd, pr);    
}

void dfs2(int nd, int pr) {
    for (auto c: adj[nd]) {
        if (c.f != pr) {
            ll nd1 = dp1[nd];
            ll nd2 = dp2[nd];
            ll c1 = dp1[c.f];
            ll c2 = dp2[c.f];
            dp1[nd] = 0; dp2[nd] = 0;
            dp1[c.f] = 0; dp2[c.f] = 0;
            calc(nd, c.f);
            calc(c.f, c.f);
            dfs2(c.f, nd);
            dp1[nd] = nd1;
            dp2[nd] = nd2;
            dp1[c.f] = c1;
            dp2[c.f] = c2;
        }
    }
    mx = max(mx, dp2[nd]);
}

int main() {
    int n; cin >> n;
    adj.assign(n, vector<P>());
    dp1.assign(n, 0);
    dp2.assign(n, 0);
    for (int i = 0; i < n-1; i++) {
        ll a, b, c; cin >> a >> b >> c;
        adj[--a].push_back({--b, c});
        adj[b].push_back({a, c});
    }
    dfs(0, 0);
    dfs2(0, 0);
    cout << mx;
    // int tst = 10;
    // dfs(tst, tst);
    // calc(0, 4);
    // calc(4, 4);
    // cout << dp2[tst] << "\n";
}

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