Submission #554197

#	Time	Username	Problem	Language	Result	Execution time	Memory
554197		dooompy	Power Plant (JOI20_power)	C++17	100 / 100	231 ms	25308 KiB

power

#include <bits/stdc++.h>

using namespace std;

vector<int> adj[200005];
string s;

int ans = 0;

int dfs(int node, int par) {
	int cur = 0;
	
	for (auto a : adj[node]) {
		if (a == par) continue;
		int t = dfs(a, node);
		
		if (s[node-1] == '1') ans = max(ans, t + 1);
		cur += t;
	}
	
	if (s[node-1] == '1') cur = max(cur-1, 1);
	ans = max(ans, cur);
	
	return cur;
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	cin >> s;
	
	dfs(1, 1);
	
	cout << ans;
}

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