Submission #1037194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037194		ajab_01	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	6040 KiB

beads

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

#define int long long

const int INF = 1e9 + 2;
const int N = 2e5 + 5;
vector<pair<int , int> > g[N];
int dp[N][2] , n;

void dfs(int v , int p){
    if((int)g[v].size() == 1 && v != 1){
        dp[v][1] = -INF;
        return;
    }
    for(auto u : g[v]){
        if(u.first == p) continue;
        dfs(u.first , v);
    }
    vector<int> vec;
    int ans = 0;
    for(auto u : g[v]){
    	if(u.first == p) continue;
        int mx = max(dp[u.first][1] + u.second , dp[u.first][0]);
        ans += mx;
        vec.push_back(dp[u.first][0] + u.second - mx);
    }
    sort(vec.begin() , vec.end());
    dp[v][1] = ans + vec.back();
    dp[v][0] = ans;
    if((int)vec.size() >= 2)
        dp[v][0] = max(dp[v][0] , dp[v][1] + vec[(int)vec.size() - 2]);
}

int32_t main(){
    cin >> n;
    for(int i = 0 ; i < n - 1 ; i++){
        int x , y , w;
        cin >> x >> y >> w;
        g[x].push_back({y , w});
        g[y].push_back({x , w});
    }
    dfs(1 , 0);
    cout << dp[1][0] << '\n';
    return 0;
}

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