제출 #621968

#제출 시각아이디문제언어결과실행 시간메모리
621968socpite구슬과 끈 (APIO14_beads)C++14
0 / 100
4 ms5056 KiB
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 2e5+5;
const int inf = 1e9;

ll dp[maxn][4];

// 1st mask: across edge
// 2nd mask: require upedge

int n;

vector<pair<int, int>> tree[maxn];

void dfs(int x, int p, int w){
    if(x != 1 && tree[x].size() == 1)dp[x][1]=w;
    else{
        ll best[4], sum = 0;
        for(int i = 0; i < 4; i++)best[i]=dp[x][i]=-inf;
        // 00 : all 00 or one 01 + w
        // 01: all 00 + w
        // 10: one 10, one 01, all 00+w || one 11, all 00+w || one 11, one 01,all 00 || two 01, all 00 || one 10, all 00
        // 11: (one 10, all 00 || one 11, one 01,all 00 ||  two 01, all 00)+w
        for(auto v: tree[x]){
            if(v.f == p)continue;
            dfs(v.f, x, v.s);
            ll base = dp[v.f][0];
            sum+=base;
            for(int i = 0; i< 4; i++)dp[v.f][i]-=base;
            dp[x][2]=max(dp[x][2], best[2]+dp[v.f][1]+w);
            dp[x][2] = max(dp[x][2], best[1] + dp[v.f][2]);
            dp[x][2] = max(dp[x][2], best[1] + dp[v.f][3]);
            dp[x][2] = max(dp[x][2], best[3] + dp[v.f][1]);
            dp[x][2] = max(dp[x][2], best[1] + dp[v.f][1]);
            dp[x][3] = max(dp[x][3], best[3] + dp[v.f][1]);
            dp[x][3] = max(dp[x][3], best[1] + dp[v.f][3]);
            dp[x][3] = max(dp[x][3], best[1] + dp[v.f][1]);
            for(int i = 0; i< 4; i++)best[i]=max(best[i], dp[v.f][i]);
        }
        dp[x][0] = max(best[1]+w, 0LL)+sum;
        dp[x][1] = sum + w;
        dp[x][2] = max({dp[x][2], best[2], best[3]+w})+sum;
        dp[x][3] = max(dp[x][3], best[2])+sum+w;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b, w;
        cin >> a >> b >> w;
        tree[a].push_back({b, w});
        tree[b].push_back({a, w});
    }
    dfs(1, 0, 0);
    cout << max(dp[1][1] , dp[1][3]);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...