Submission #382313

#	Time	Username	Problem	Language	Result	Execution time	Memory
382313		pure_mem	Beads and wires (APIO14_beads)	C++14	0 / 100	3 ms	2688 KiB

beads

#include <iostream>
#include <vector>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12;
const int INF = 1e9;

int n, dp[2][N], ans;
vector< pair<int, int> > g[N];

void dfs(int v, int pr){
	dp[0][v] = -INF;
	for(pair<int, int> tmp: g[v]){
		int to = tmp.X, cost = tmp.Y;
		if(to != pr){
			dfs(to, v);
			dp[1][v] += max(dp[1][to], dp[0][to] + cost);	
		}
	} 
	int sum = dp[1][v], c1 = -INF, c2 = -INF;
	for(pair<int, int> tmp: g[v]){
		int to = tmp.X, cost = tmp.Y;
		if(to != pr){
			int dt = cost;
			if(dp[1][to] < dp[0][to] + cost)
				dt = dp[1][to] - dp[0][to];
			if(c1 < dt)
				c2 = c1, c1 = dt;
			else if(c2 < dt)
				c2 = dt;
		}
	}
	if(c1 != -INF)
		dp[0][v] = sum + c1;
	if(c2 != -INF)
		dp[1][v] = max(dp[1][v], sum + c2 + c1);
	ans = max(ans, dp[1][v]);
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1, x, y, z;i < n;i++){
		cin >> x >> y >> z;
		g[x].push_back(MP(y, z));
		g[y].push_back(MP(x, z));
	}
	dfs(1, 1);
	//cerr << dp[0][6] << "\n";
	cout << ans;
}

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