제출 #230944

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;
using ll=long long;

const int MX_N = 2e5+5;
const int INF = 2e9+10;

int N;
vector<ii> al[MX_N];

ll f[MX_N][2];

void DFS(int u, int p) {
    for (ii v : al[u]) if (v.first != p) {
        DFS(v.first,u);
    }

    ll best[2] = {-INF, -INF};
    for (ii v : al[u]) if (v.first != p) {
        if (f[v.first][1] > f[v.first][0]) {
            f[u][0] += f[v.first][1] + v.second;
            f[u][1] += f[v.first][1] + v.second;

            ll x = f[v.first][0]-f[v.first][1];
            if (x > best[0]) swap(x,best[0]);
            if (x > best[1]) swap(x,best[1]);
        } else {
            f[u][0] += f[v.first][0];
            f[u][1] += f[v.first][0];

            ll x = v.second;
            if (x > best[0]) swap(x,best[0]);
            if (x > best[1]) swap(x,best[1]);
        }
    }

    if (best[0] > -INF && best[1] > -INF)
        f[u][0] += max(0LL, best[0] + best[1]);
    if (best[0] > -INF) f[u][1] += best[0];
    else f[u][1] = -INF;
    //TRACE(u _ 1 _ f[u][0] _ f[u][1] _ best[0] _ best[1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int A, B, C; cin >> A >> B >> C;
        al[A].emplace_back(B,C);
        al[B].emplace_back(A,C);
    }

    DFS(1,0);
    cout << f[1][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...