Submission #230944

#	Time	Username	Problem	Language	Result	Execution time	Memory
230944		lyc	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	4992 KiB

beads

#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];
}

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