제출 #618218

#제출 시각아이디문제언어결과실행 시간메모리
618218penguinhackerPower Plant (JOI20_power)C++17
100 / 100
148 ms28896 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, ans, dp[mxN];
string s;
vector<int> adj[mxN];

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin >> s;
	dfs();
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...