Submission #943611

#TimeUsernameProblemLanguageResultExecution timeMemory
943611aqxaPower Plant (JOI20_power)C++17
100 / 100
149 ms34564 KiB
#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const int N = 2e5 + 10; 

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

	int n; 
	cin >> n; 
	vector<vector<int>> g(n); 
	for (int i = 0; i < n - 1; ++i) {
		int x, y; 
		cin >> x >> y; 
		x--; y--; 
		g[x].push_back(y); 
		g[y].push_back(x); 
	}
	string s; 
	cin >> s; 

	int ans = 0; 
	vector<int> dp(n, 0); 
	function<void(int, int)> dfs = [&] (int x, int p) {
		int c = 0, mx = 0; 
		for (auto y: g[x]) {
			if (y != p) {
				dfs(y, x); 
				c += dp[y]; 
				mx = max(mx, dp[y]); 
			}
		}
		
		if (s[x] == '1') {
			ans = max(ans, 1 + mx); 
			ans = max(ans, c - 1); 
			dp[x] = max(1, max(c - 1, mx - 1)); 
		} else {
			dp[x] = max(c, 0); 
			ans = max(ans, dp[x]); 
		}
	}; 
	dfs(0, -1); 

	// for (int i = 0; i < n; ++i) cout << dp[i] << '\n';
	
	cout << ans << "\n";

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...