Submission #962482

#TimeUsernameProblemLanguageResultExecution timeMemory
9624820npataPower Plant (JOI20_power)C++17
100 / 100
200 ms29668 KiB
#include<bits/stdc++.h>
using namespace std;

const int N = 200'000;

#define vec vector
#define pb push_back

int dp[N][2];
vec<int> tree[N];
string s;

void dfs(int u, int p = -1) {
	for(int v : tree[u]) {
		if(p==v) continue;

		dfs(v, u);
	}

	int a = 1; int b = -1; int c = 0;
	for(int v : tree[u]) {
		if(v==p) continue;
		a = max(dp[v][1]+1, a);
		b += dp[v][1];
		c = max(dp[v][0], c);
	}
	if(s[u] == '1') {
		dp[u][0] = max(max(a, b), c);
		dp[u][1] = max(b, 1);
	}
	else {
		dp[u][1] = b+1;
		dp[u][0] = max(c, b+1);
	}
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i<n-1; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;

		tree[u].pb(v);
		tree[v].pb(u);
	}

	cin >> s;

	dfs(0);

	cout << dp[0][0] << '\n';

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