Submission #399952

#	Time	Username	Problem	Language	Result	Execution time	Memory
399952		nikatamliani	Power Plant (JOI20_power)	C++14	100 / 100	168 ms	31592 KiB

power

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> edges[N];
int dp[N], ans, n;
string s;
void solve(int x, int p) {
	int sum = 0, maxi = 0;
	for(int to : edges[x]) {
		if(to != p) {
			solve(to, x);
			sum += dp[to];
			maxi = max(maxi, dp[to]);
		}
	}
	if(s[x] == '1') {
		dp[x] = max(sum-1, 1);
		ans = max(ans, maxi+1);
		ans = max(ans, sum-1);
	} else {
		dp[x] = sum;
		ans = max(ans, sum);
	}
	ans = max(ans, dp[x]);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; ++i) {
		int u, v; cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	cin >> s; s = "@" + s;
	solve(1, 0);
	cout << ans << endl;
}

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