Submission #670251

#	Time	Username	Problem	Language	Result	Execution time	Memory
670251		fatemetmhr	Beads and wires (APIO14_beads)	C++17	28 / 100	1075 ms	1108 KiB

beads

// hmmm... na dige chizi baraye goftan namoonde


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 1e4 + 10;
const int lg    = 20;
const ll  inf   = 1e18;

int dp[2][maxn5];
vector <pair<int, int>> adj[maxn5];

void dfs(int v, int par){
    for(auto [u, w] : adj[v]) if(u != par){
        dp[1][u] = w;
        dfs(u, v);
        dp[0][v] = max(dp[0][v] + dp[0][u], dp[1][v] + dp[1][u]);
        dp[1][v] += dp[0][u];
    }
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n - 1; i ++){
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    int ans = 0;
    for(int i = 0; i < n; i++){ // YOU HAVE CHANGED THIS
        memset(dp, 0, sizeof dp);
        dfs(i, -1);
        ans = max(ans, dp[1][i]);
    }

    cout << ans << endl;

}

/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

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