Submission #1109803

#TimeUsernameProblemLanguageResultExecution timeMemory
1109803SharkyBeads and wires (APIO14_beads)C++17
100 / 100
110 ms33720 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 10;
const int inf = 1e13;

int n, dp[N][2][2];
vector<pair<int, int>> adj[N];

void dfs(int u, int p) {
    dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = -inf;
    vector<pair<int, int>> vec;
    int non_root = 0;
    for (auto& [v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        non_root++;
        dp[u][0][0] += max(dp[v][0][1] + w, dp[v][0][0]);
        vec.push_back({dp[v][0][0] + w - max(dp[v][0][1] + w, dp[v][0][0]), v});
    }
    if (non_root == 0) return;
    int sum = dp[u][0][0];
    sort(vec.begin(), vec.end(), [] (auto a, auto b) { return a.first > b.first; });
    dp[u][0][1] = dp[u][0][0] + vec[0].first;
    for (auto& [v, w] : adj[u]) {
        if (v == p) continue;
        dp[u][1][1] = max(dp[u][1][1], sum + max(dp[v][0][0], dp[v][1][0]) + w - max(dp[v][0][0], dp[v][0][1] + w));
        dp[u][1][0] = max(dp[u][1][0], sum + max(dp[v][1][0], dp[v][1][1] + w) - max(dp[v][0][0], dp[v][0][1] + w));
        if (vec[0].second != v) dp[u][1][0] = max(dp[u][1][0], sum + max(dp[v][1][0], dp[v][0][0]) + w - max(dp[v][0][0], dp[v][0][1] + w) + vec[0].first);
        else if (vec.size() > 1) dp[u][1][0] = max(dp[u][1][0], sum + max(dp[v][1][0], dp[v][0][0]) + w - max(dp[v][0][0], dp[v][0][1] + w) + vec[1].first);
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, -1);
    cout << max(dp[1][0][0], dp[1][1][0]) << '\n';
}

/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...