제출 #444918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444918		dutch	Power Plant (JOI20_power)	C++17	100 / 100	174 ms	24860 KiB

power

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

const int MAXN = 2e5;

int n, ans, dp[MAXN];
vector<int> g[MAXN];
string s;

void dfs(int u, int p){
	dp[u] = -1 * (s[u] - '0');
	for(int &v : g[u]) if(v - p){
		dfs(v, u);
		ans = max(ans, s[u] - '0' + dp[v]);
		dp[u] += dp[v];
	}
	dp[u] = max(dp[u], s[u] - '0');
	ans = max(ans, dp[u]);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<n; ++i){
		int u, v; cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cin >> s;
	dfs(0, 0);
	cout << ans;
}

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