Submission #198218

#	Time	Username	Problem	Language	Result	Execution time	Memory
198218		Atalasion	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int dp[N][2], n;
vector<pii> G[N];

void DFS(int v = 1, int p = 1){
	ll sm = 0;
	if (G[v].size() == 1 && v != 1) dp[v][1] = -INF;
	for (auto u:G[v]){
		if (u.F == p) continue;
		DFS(u.F, v);
		sm += max(dp[u.F][0], dp[u.F][1] + u.S);
	}
	for (auto u:G[v]){
		if (u.F == p) continue;
		dp[v][1] = max(dp[v][1], sm - max(dp[u.F][0], dp[u.F][1] + u.S) + u.S + dp[u.F][0]);
	}
	for (auto u:G[v]){
		for (auto x:G[v]){
			if (u.F == p || x.F == p) continue;
			if (u.F == x.F) continue;
			dp[v][0] = max(dp[v][0], sm - max(dp[u.F][0], dp[u.F][1] + u.S) - max(dp[x.F][0], dp[x.F][1] + x.S) + dp[u.F][0] + u.S + dp[x.F][0] + x.S);
		}
	}
	dp[v][0] = max(dp[v][0], sm);
	//cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << '\n';
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u, c;
		cin >> v >> u >> c;
		G[v].pb({u, c});
		G[u].pb({v, u});
	}
	DFS();
	cout << dp[1][0];













	return 0;
}

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