제출 #1175323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175323		guilhermecpp	Beads and wires (APIO14_beads)	C++20	100 / 100	205 ms	43260 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define N 200010
#define M 2
#define INF 1000000000000000000
#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;

ll n;
vll grafo[N];

pll invalid = {-INF, -INF};

ll sum[N];
pll best[N][M];
ll dp[N][2];

ll copySum[N];
pll copyBest[N][M];
ll copyDp[N][2];

ll ans[N];

void Add(ll u, pll val)
{

	best[u][M-1] = max(best[u][M-1], val);
    
    sort(best[u], best[u] + M, greater< pll >());

	return;

}

void Rem(ll u, pll val)
{

    for(ll i = 0;i < M;i++)
        if(best[u][i].se == val.se)
            best[u][i] = invalid;

    sort(best[u], best[u] + M, greater< pll >());

    return;

}

void Copy(pll a[M], pll b[M])
{

    for(ll i = 0;i < M;i++) b[i] = a[i];

    return;

}

void DFS(ll u, ll pai, ll wpai)
{

    for(ll i = 0;i < M;i++) best[u][i] = invalid;

    ll a, b;

    for(auto [v, w] : grafo[u])
    {

        if(v == pai) continue;

        DFS(v, u, w);

        sum[u] += dp[v][0];
        Add(u, {(dp[v][1] + w) - dp[v][0], v});

    }

    dp[u][1] = sum[u];

    dp[u][0] = dp[u][1];
    dp[u][0] = max(dp[u][0], sum[u] + best[u][0].fi + wpai);

    return;

}

void Solv(ll u, ll pai)
{

    ans[u] = dp[u][1];

    copySum[u] = sum[u];
    Copy(best[u], copyBest[u]);
    for(ll i = 0;i <= 1;i++) copyDp[u][i] = dp[u][i];

    for(auto [v, w] : grafo[u])
    {

        if(v == pai) continue;

        sum[u] -= dp[v][0];
        Rem(u, {(dp[v][1] + w) - dp[v][0], v});
        
        dp[u][1] = sum[u];
        dp[u][0] = dp[u][1];
        dp[u][0] = max(dp[u][0], sum[u] + best[u][0].fi + w);
        
        sum[v] += dp[u][0];
        Add(v, {(dp[u][1] + w) - dp[u][0], u});
        dp[v][1] = sum[v];
        dp[v][0] = dp[v][1];

        Solv(v, u);
        
        sum[u] = copySum[u];
        Copy(copyBest[u], best[u]);
        for(ll i = 0;i <= 1;i++) dp[u][i] = copyDp[u][i];

    }

    return;

}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll u, v, w, i;

    cin >> n;

    for(i = 1; i < n; i++)
    {

        cin >> u >> v >> w;

        grafo[u].pb({v, w});
        grafo[v].pb({u, w});

    }

    DFS(1, 1, -INF);
	Solv(1, 1);

	ll resp = 0;
	for(i = 1;i <= n;i++) resp = max(resp, ans[i]);

    cout << resp << endl;

    return 0;

}

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