제출 #1175020

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

#define N 200010
#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];

ll dp[N][2];
// 0: aresta do pai não foi pega
// 1: aresta do pai já foi pega

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

    ll sum, a, b;

    sum = 0;
    a = -INF;

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

        if(v == pai) continue;

        DFS(v, u, w);

        sum += dp[v][0];

        a = max(a, (dp[v][1] + w) - dp[v][0]);

    }

    dp[u][1] = sum;

    dp[u][0] = dp[u][1];
    dp[u][0] = max(dp[u][0], sum + a + wpai);

    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});

    }

    ll x = 0;

    DFS(1, 1, -INF);
    x = dp[1][1];

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

        DFS(i, i, -INF);
        x = max(x, dp[i][1]);

    }

    cout << x << endl;

    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...