Submission #31618

#	Time	Username	Problem	Language	Result	Execution time	Memory
31618		ToMo01	Beads and wires (APIO14_beads)	C++14	28 / 100	1060 ms	7552 KiB

beads

/*input
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 200007;

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

void dfs(int u){
	for(auto v:child[u]){
		if(v.first == par[u]) continue;
		par[v.first] = u;
		dfs(v.first);
		dp[u][0] += max(dp[v.first][0], dp[v.first][1] + v.second);
	}

	for(auto v:child[u])
		if(v.first != par[u])
			dp[u][1] = max(dp[u][1], dp[u][0] + dp[v.first][0] + v.second - max(dp[v.first][0], dp[v.first][1] + v.second));
} 

int main(){
	cin >> n;
	for(int i = 1; i < n; ++i){
		int u, v, w; cin >> u >> v >> w;
		child[u].push_back({v, w});
		child[v].push_back({u, w});
	}	

	for(int i = 1; i <= n; ++i){
		memset(par, 0, sizeof par);
		memset(dp, 0, sizeof dp);

		for(int j = 1; j <= n; ++j)
			dp[j][1] = INT_MIN;

		dfs(i);
		ans = max(ans, dp[i][0]);
	}

	cout << ans << endl;
}

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