Submission #31613

#	Time	Username	Problem	Language	Result	Execution time	Memory
31613		aome	Beads and wires (APIO14_beads)	C++14	28 / 100	1080 ms	5504 KiB

beads

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

typedef pair<int, int> ii;
const int N = 200005;

int n, f[N][2];
vector<ii> G[N];

void dfs(int u, int p) {
    f[u][0] = 0;
    for (auto v : G[u]) {
        if (v.fi == p) continue;
        dfs(v.fi, u);
    }
    int mx = -1e9;
    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;
}

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));
    }
    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: 0 / 29
• Subtask 4: 0 / 43