Submission #316947

#	Time	Username	Problem	Language	Result	Execution time	Memory
316947		manh9203	Power Plant (JOI20_power)	C++17	100 / 100	211 ms	29732 KiB

power

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 200005;

int n;
string s;
vector<int> adj[N];
int dp[N][2];

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

int 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].push_back(v);
		adj[v].push_back(u);
	}
	cin >> s; s = " " + s;

	dfs(1, 1);
	cout << max(dp[1][0], dp[1][1]);
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53