제출 #329282

#제출 시각아이디문제언어결과실행 시간메모리
329282terencehillPower Plant (JOI20_power)C++14
100 / 100
202 ms31660 KiB
#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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...