제출 #625274

#제출 시각아이디문제언어결과실행 시간메모리
625274GusterGoose27구슬과 끈 (APIO14_beads)C++11
0 / 100
4 ms5032 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5;
int n;
int dp[MAXN][2]; // open, closed
vector<pii> edges[MAXN];
int par_val[MAXN];

struct comp {
	bool operator()(int &a, int &b) {
		return a > b;
	}
} comp;

void dfs(int cur = 0, int p = -1) {
	int o_sum = 0;
	vector<int> diffs;
	for (pii edge: edges[cur]) {
		int next = edge.first;
		if (next == p) continue;
		par_val[next] = edge.second;
		dfs(next, cur);
		o_sum += dp[next][0];
		diffs.push_back(edge.second+dp[next][1]-dp[next][0]);
	}
	sort(diffs.begin(), diffs.end(), comp);
	int ex = 0;
	if (diffs.size() >= 2) ex = diffs[0]+diffs[1];
	dp[cur][1] = max(ex, 0)+o_sum;
	if (diffs.size() == 1 || (diffs.size() >= 2 && par_val[cur] > diffs[1])) ex = diffs[0]+par_val[cur];
	dp[cur][0] = max(ex, 0)+o_sum;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y, w;
		cin >> x >> y >> w; x--; y--;
		edges[x].push_back(pii(y, w));
		edges[y].push_back(pii(x, w));
	}
	dfs();
	cout << dp[0][1] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...