Submission #31630

#	Time	Username	Problem	Language	Result	Execution time	Memory
31630		aome	Beads and wires (APIO14_beads)	C++14	100 / 100	247 ms	22380 KiB

beads

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

typedef pair<int, int> ii;
const int N = 200005;
const int INF = -1e9;

int n, res;
int f[N][2], g[N][2];
int L[N], R[N];
vector<ii> G[N];

void dfs(int u, int p) {
    for (auto v : G[u]) {
        if (v.fi == p) continue;
        dfs(v.fi, u);
    }
    int mx = INF;
    for (auto v : G[u]) {
        if (v.fi == p) continue;
        int vMx = max(f[v.fi][0], f[v.fi][1] + v.se);
        f[u][0] += vMx;
        mx = max(mx, f[v.fi][0] + v.se - vMx);
    }
    f[u][1] = f[u][0] + mx;
}

void reDfs(int u, int p) {
    vector<ii> _G;
    for (auto v : G[u]) {
        if (v.fi == p) continue;
        _G.push_back(v);
    }
    int sz = _G.size(), sum = 0;
    L[0] = INF, R[sz + 1] = INF;
    for (int i = 1; i <= sz; ++i) {
        ii v = _G[i - 1];
        sum += max(f[v.fi][0], f[v.fi][1] + v.se);
        int vMx = max(f[v.fi][0], f[v.fi][1] + v.se);
        L[i] = max(L[i - 1], f[v.fi][0] + v.se - vMx);
    }
    for (int i = sz; i >= 1; --i) {
        ii v = _G[i - 1];
        int vMx = max(f[v.fi][0], f[v.fi][1] + v.se);
        R[i] = max(R[i + 1], f[v.fi][0] + v.se - vMx);
    }
    for (int i = 1; i <= sz; ++i) {
        ii v = _G[i - 1];
        int mx = max(L[i - 1], R[i + 1]);
        int tSum = sum - max(f[v.fi][0], f[v.fi][1] + v.se);
        tSum += g[u][0], mx = max(mx, g[u][1] - g[u][0]);
        // f0 = tSum, f1 = tSum + mx;
        g[v.fi][0] = max(tSum, tSum + mx + v.second), g[v.fi][1] = tSum + v.second;
    }
    //cout << u << ' ' << f[u][0] << ' ' << f[u][1] << '\n';
    //cout << u << ' ' << g[u][0] << ' ' << g[u][1] << '\n';
    res = max(res, f[u][0] + g[u][0]);
    for (auto v : _G) reDfs(v.fi, u);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(ii(v, w));
        G[v].push_back(ii(u, w));
    }
    dfs(1, 1);
    g[1][1] = INF;
    res = f[1][0];
    reDfs(1, 1);
    cout << res;
//    int res = 0;
//    for (int i = 1; i <= n; ++i) {
//        dfs(i, i), res = max(res, f[i][0]);
//    }
//    cout << res;
}

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