Submission #532879

#TimeUsernameProblemLanguageResultExecution timeMemory
532879vuhoanggiapPower Plant (JOI20_power)C++17
100 / 100
153 ms28688 KiB
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int maxN = 2e5 + 5; 
int n, ans; 
bool has[maxN];
int dp[maxN];
vector<int> adj[maxN];

void dfs(int u, int p = 1) { 
	for (auto v : adj[u]) {
		if (v != p) {
			dfs(v, u); 
			dp[u] += dp[v]; 
			ans = max(ans, dp[v] + has[u]); 
		}
	}
	if (has[u]) 
		dp[u] = max(dp[u] - 1, 1); 
	dp[u] = max(dp[u], 0); 
	ans = max(ans, dp[u]); 
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	cin >> n; 
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v; 
		adj[u].pb(v); adj[v].pb(u); 
	}
	for (int i = 1; i <= n; i++) {
		char c; cin >> c; 
		has[i] = (c == '1'); 
	}
	dfs(1); 
	cout << ans; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...