Submission #1037194

#TimeUsernameProblemLanguageResultExecution timeMemory
1037194ajab_01Beads and wires (APIO14_beads)C++17
0 / 100
1 ms6040 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...