제출 #622081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
622081		socpite	구슬과 끈 (APIO14_beads)	C++14	100 / 100	188 ms	28968 KiB

beads

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 2e5+5;
const ll inf = 1e15;

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;
        dp[x][2]=-inf;
        dp[x][3]=-inf;
    }
    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 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][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][3], best[2], best[3]+w})+sum;
        dp[x][3] = max(dp[x][3], best[2])+sum+w;
        //for(int i = 0; i < 4; i++)cout << x << " " << i << " " << dp[x][i] << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //ifstream cin("input.txt");
    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]);
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43