Submission #31613

#TimeUsernameProblemLanguageResultExecution timeMemory
31613aomeBeads and wires (APIO14_beads)C++14
28 / 100
1080 ms5504 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...