Submission #1121269

#TimeUsernameProblemLanguageResultExecution timeMemory
1121269PagodePaivaBeads and wires (APIO14_beads)C++17
0 / 100
7 ms8272 KiB
#include<bits/stdc++.h>

using namespace std;

const int N = 200010;
vector <pair <int, int>> g[N];
int dp[N][2][2];
const int inf = 2e9;

void dfs(int v, int f1, int f2, int p){
    if(dp[v][f1][f2] != -1) return;
    for(auto [x, w] : g[v]){
        if(x == p) continue;
        dfs(x, 0, 0, v);
        dfs(x, 0, 1, v);
        dfs(x, 1, 0, v);
        dfs(x, 1, 1, v);
    }
    if(f1 == 0 and f2 == 0){
        dp[v][f1][f2] = 0;
        int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
        for(auto [x, w] : g[v]){
            if(x == p) {
                if(w > best1){
                    best2 = best1;
                    best1 = w;
                }
                else if(w > best2){
                    best2 = w;
                }
                continue;
            }
            sum += dp[x][0][0];
            sum2 += dp[x][1][0];
            if(best1 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = best1;
                best1 = dp[x][1][1]+w-dp[x][1][0];
            }
            else if(best2 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = dp[x][1][1]+w-dp[x][1][0];
            }
        }
        dp[v][f1][f2] = sum;
        if(best2 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
        return;
    }
    if(f1 == 1 and f2 == 0){
        dp[v][f1][f2] = 0;
        int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
        for(auto [x, w] : g[v]){
            if(x == p) {
                best2 = w;
                continue;
            }
            sum += dp[x][0][0];
            sum2 += dp[x][1][0];
            if(best1 < dp[x][1][1]+w-dp[x][1][0]){
                best1 = dp[x][1][1]+w-dp[x][1][0];
            }
        }
        dp[v][f1][f2] = sum;
        if(best2 != -inf and best1 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
        return;
    }
    if(f1 == 0 and f2 == 1){
        dp[v][f1][f2] = 0;
        int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
        for(auto [x, w] : g[v]){
            if(x == p) {
                continue;
            }
            sum += dp[x][0][0];
            sum2 += dp[x][1][0];
            if(best1 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = best1;
                best1 = dp[x][1][1]+w-dp[x][1][0];
            }
            else if(best2 < dp[x][1][1]+w-dp[x][1][0]){
                best2 = dp[x][1][1]+w-dp[x][1][0];
            }
        }
        dp[v][f1][f2] = sum;
        if(best2 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
        return;
    }
    dp[v][f1][f2] = 0;
    int sum = 0, sum2 = 0, best1 = -inf, best2 = -inf;
    for(auto [x, w] : g[v]){
        if(x == p) {
            continue;
        }
        sum += dp[x][0][0];
        sum2 += dp[x][1][0];
        if(best1 < dp[x][1][1]+w-dp[x][1][0]){
            best2 = best1;
            best1 = dp[x][1][1]+w-dp[x][1][0];
        }
        else if(best2 < dp[x][1][1]+w-dp[x][1][0]){
            best2 = dp[x][1][1]+w-dp[x][1][0];
        }
    }
    dp[v][f1][f2] = sum;
    if(best2 != -inf) dp[v][f1][f2] = max(dp[v][f1][f2], sum2+best1+best2);
    return;
}

int main(){
    memset(dp, -1, sizeof dp);
    int n;
    cin >> n;
    for(int i = 1;i < n;i++){
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    dfs(1, 0, 1, 1);
    cout << dp[1][0][1] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...