Submission #347394

#	Time	Username	Problem	Language	Result	Execution time	Memory
347394		dolphingarlic	Power Plant (JOI20_power)	C++14	100 / 100	192 ms	26156 KiB

power

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

string s;
vector<int> g[200001];
int dp[200001], r = 1;

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> s;
	dfs();
	cout << r << '\n';
	return 0;
}

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