Submission #44740

#	Time	Username	Problem	Language	Result	Execution time	Memory
44740		platypus	Beads and wires (APIO14_beads)	C++17	0 / 100	9 ms	9600 KiB

beads

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int N;
vector<pair<int, LL>>graph[234567];
int par[234567];
LL pcost[234567];

void dfs(int v, int las, LL cst) {
	par[v] = las;
	pcost[v] = cst;
	for (auto next : graph[v]) {
		if (next.first == las)continue;
		dfs(next.first, v, next.second);
	}
}

LL memo[2][234567];
LL dp(bool c, int v) {
	if (memo[c][v] >= 0)return memo[c][v];
	LL ans = 0;
	vector<LL>vec;
	for (auto next : graph[v]) {
		int ch = next.first;
		if (ch == par[v])continue;
		LL dpn = dp(0, ch);
		LL dpc = dp(1, ch);
		LL dpv = max(dpc, dpn);
		LL loss = dpn - dpv;
		loss += next.second;
		vec.push_back(loss);
		ans += dpv;
	}
	sort(vec.rbegin(), vec.rend());
	if (c) {
		if (vec.size() > 0) {
			LL can = ans;
			can += vec[0];
			can += pcost[v];
			ans = max(ans, can);
		}
	}
	else {
		if (vec.size() > 1) {
			LL can = ans;
			can += vec[0];
			can += vec[1];
			ans = max(ans, can);
		}
	}
	return memo[c][v] = ans;
}

int main(void)
{
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int u, v; LL cost;
		cin >> u >> v >> cost;
		--u; --v;
		graph[u].push_back({ v,cost });
		graph[v].push_back({ u,cost });
	}
	dfs(0, -1, 0);
	memset(memo, 0xff, sizeof(memo));
	LL ans = dp(0, 0);
	cout << ans << endl;
	return 0;
}

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