Submission #365083

#	Time	Username	Problem	Language	Result	Execution time	Memory
365083		saleh	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	5100 KiB

beads

#include <bits/stdc++.h>

#define ft first
#define sd second
#define int long long

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 200 * 1000 + 23;






/*
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
*/







struct chi {
	int x = INT_MIN, y = INT_MIN;
	void f(int z) {
		if (x < z) {
			y = x;
			x = z;
		} else y = max(y, z);
	}
};


int n, dp[2 + 2][MAXN];
vector<pii> g[MAXN];

void dfs(int v, int p, int val) {
	vector<pii> vec;
	for (auto i : g[v]) if (i.ft != p) {
		dfs(i.ft, v, i.sd);
		vec.push_back(i);
	}
	if (vec.empty()) return;
	int tmp = 0, tmx = INT_MIN;
	for (auto i : vec) tmp += dp[1][i.ft];
	dp[0][v] = dp[1][v] = tmp;
	for (auto i : vec) if (tmx < i.sd + dp[0][i.ft] - dp[1][i.ft]) tmx = i.sd + dp[0][i.ft] - dp[1][i.ft];
	dp[1][v] = max(tmp, tmp + tmx + val);
	chi h;
	for (auto i : vec) h.f(i.sd + dp[0][i.ft] - dp[1][i.ft]);
	dp[0][v] = max(dp[0][v], tmp + h.x + h.y);
	dp[1][v] = max(dp[1][v], tmp + h.x + h.y);
}



int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	{
		int a, b, c;
		for (int i = 1; i < n; i++) {
			cin >> a >> b >> c;
			g[--a].push_back({--b, c}), g[b].push_back({a, c});
		}
	}
	dfs(0, -1, INT_MIN);
	cout << dp[1][0];
	return 0;
}

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