Submission #329282

#	Time	Username	Problem	Language	Result	Execution time	Memory
329282		terencehill	Power Plant (JOI20_power)	C++14	100 / 100	202 ms	31660 KiB

power

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, ans = 0;
string s;
vector<vector<int>> adj;
vector<int> dp;

void bfs(int node, int parent) {
	int mx = 0, sum = 0, val = s[node] - '0';
	for(int i : adj[node]) {
		if(i == parent) continue;
		bfs(i, node);
		
		mx = max(mx, dp[i]);
		sum += dp[i];
	}
	
	ans = max(ans, mx + val);
	ans = max(ans, sum - val);
	
	dp[node] = max(dp[node], mx - val);
	dp[node] = max(dp[node], sum - val);
	dp[node] = max(dp[node], val);
	
	ans = max(ans, dp[node]);
} 

void solve() {
	cin >> n;
	
	dp.resize(n, 0); adj.resize(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	cin >> s;
	
	bfs(0, -1);
	
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	solve();
}

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