제출 #684946

#제출 시각아이디문제언어결과실행 시간메모리
684946NK_Power Plant (JOI20_power)C++17
100 / 100
177 ms29632 KiB
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	
	vector<vector<int>> adj(N);

	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	string S; cin >> S;

	vector<int> on(N); for(int i = 0; i < N; i++) on[i] = S[i] - '0';
	vector<int> dp(N, 0);

	function<void(int, int)> gen = [&](int u, int p) {
		dp[u] = -(S[u] - '0');
		for(auto v : adj[u]) if (v != p) {
			gen(v, u);
			dp[u] += max(dp[v], on[v]);
		}
		// cout << u << " " << max(dp[u], on[u]) << nl;
	};

	gen(0, -1);

	int ans = 0;

	function<void(int, int)> dfs = [&](int u, int p) {
		// cout << u << " " << dp[u] << nl;
		ans = max(ans, max(dp[u], on[u]));

		for(auto v : adj[u]) if (v != p) {
			ans = max(ans, max(dp[v], on[v]) + on[u]);

			dp[u] -= max(dp[v], on[v]);
			dp[v] += max(dp[u], on[u]);

			dfs(v, u);

			dp[v] -= max(dp[u], on[u]);
			dp[u] += max(dp[v], on[v]);
		}
	};

	dfs(0, -1);

	cout << ans << nl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...