Submission #106070

#	Time	Username	Problem	Language	Result	Execution time	Memory
106070		Saboon	구슬과 끈 (APIO14_beads)	C++14	0 / 100	6 ms	5120 KiB

beads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 10;
const int inf = 1e9;

int dp[maxn], pd[maxn];
vector<pair<int, int> > t[maxn];

pair<int,int> merge(pair<int,int> twomax, int k){
	if (k > twomax.second)
		twomax.second = k;
	if (twomax.first < twomax.second)
		swap(twomax.first, twomax.second);
	return twomax;
}

void dfs(int v, int par = -1){
	int sum = 0;
	pair<int,int> twomax = {-inf, -inf}; 
	for (auto edge : t[v]){
		int u = edge.first, c = edge.second;
		if (u != par){
			dfs(u, v);
			ll mx = max(dp[u], pd[u] + c);
			sum += mx;
			twomax = merge(twomax, dp[u] + c - mx);
		}
	}
	int extra = max(0, twomax.first + twomax.second);
	dp[v] = sum + extra;
	pd[v] = sum + twomax.first;
}

int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int v, u, c;
		cin >> v >> u >> c;
		t[v].push_back({u, c});
		t[u].push_back({v, c});
	}
	dfs(1);
	cout << dp[1] << endl;
}

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