제출 #347394

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