제출 #1015779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015779		MohamedFaresNebili	구슬과 끈 (APIO14_beads)	C++14	0 / 100	2 ms	11356 KiB

beads

#include <bits/stdc++.h>
	
		using namespace std;

		int N;
		int best[200005];
		vector<pair<int, int>> adj[200005];
		int DP[200005], cur[200005];
		int maxW[200005][2], sum[200005];

		int nDP[200005], ncur[200005];
		int nsum[200005];

		void dfs(int v, int p) {
			maxW[v][0] = maxW[v][1] = -1e9;
			
			for(auto u : adj[v]) {
				if(u.first == p) continue;
				dfs(u.first, v); 
				sum[u.first] = max(DP[u.first], u.second + cur[u.first]);
				DP[v] += sum[u.first];
				maxW[v][1] = max(maxW[v][1], u.second + DP[u.first] - sum[u.first]);
				if(maxW[v][0] < maxW[v][1])
					swap(maxW[v][0], maxW[v][1]);
			}

			cur[v] = maxW[v][0] + DP[v];

		}

		void solve(int v, int p, int preW, int preC) {
			if(v != -1) {
				nDP[v] = DP[p] - sum[v] + nsum[p];
				int c = maxW[p][0];
				if(preW + DP[v] - sum[v] == c)
					c = maxW[p][1];
				c = max(c, preC);
				ncur[v] = c + nDP[v];
				nsum[v] = max(nDP[v], preW + ncur[v]);
				preC = preW + nDP[v] - nsum[v];
			}
			for(auto u : adj[v]) {
				if(u.first == p) continue;
				solve(u.first, v, u.second, preC);
			}
		}

		int32_t main() {
			ios_base::sync_with_stdio(0);
			cin.tie(0); cout.tie(0);

			cin >> N;
			for(int l = 0; l < N - 1; l++) {
				int U, V, W; cin >> U >> V >> W;
				adj[U].push_back({V, W});
				adj[V].push_back({U, W});
			}
			dfs(1, 1); solve(1, -1, 0, -1e9);
			int res = 0;
			for(int l = 1; l <= N; l++) 
				res = max(res, DP[l] + nsum[l]);
			cout << res << "\n";
		}

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