Submission #805889

#	Time	Username	Problem	Language	Result	Execution time	Memory
805889		rxlfd314	Power Plant (JOI20_power)	C++17	100 / 100	109 ms	30860 KiB

power

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

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;
	cin >> N;
	vector<int> adj[N];
	for (int i = 1, a, b; i < N; i++) {
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	string S;
	cin >> S;
	
	int ans = 0;
	function<int(int, int)> dfs = [&](int i, int p) {
		int tot = 0, mx = 0;
		for (int j : adj[i]) {
			if (j == p) continue;
			int v = dfs(j, i);
			tot += v;
			mx = max(mx, v);
		}
		ans = max({ans, mx + S[i] - '0', tot - S[i] + '0'});
		return max(S[i] - '0', tot - S[i] + '0');
	};
	
	dfs(0, 0);
	cout << ans << '\n';
}

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