Submission #1032541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032541		juicy	Power Plant (JOI20_power)	C++17	100 / 100	102 ms	31032 KiB

power

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n;
char s[N];
int dp[N], sum[N], f[N], mx[N];
vector<int> g[N];

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

int res = 0;

void reroot(int u, int p) {
	if (s[u] == '1') {
		res = max({res, f[u] + sum[u] - 1, max(f[u], mx[u]) + 1});
	}
	for (int v : g[u]) {
		if (v != p) {
			if (s[u] == '1') {
				f[v] = max(1, sum[u] - dp[v] + f[u] - 1);
			} else {
				f[v] = sum[u] - dp[v] + f[u];
			}
			reroot(v, u);
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	dfs(1, 1);
	reroot(1, 1);
	cout << res;
	return 0;
}

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