제출 #434924

#제출 시각아이디문제언어결과실행 시간메모리
434924xuliuPower Plant (JOI20_power)C++14
0 / 100
5 ms5812 KiB
#include <bits/stdc++.h>
using namespace std;

// Power - subtask 2

#define ll long long
#define ull unsigned LL
#define ld long double
#define debug if(0)
#define fastio ios_base::sync_with_stdio(0); cin.tie()

const int N = 2e5 + 4;
string s;
vector<int> V[N], dp(N, 0);
bool vis[N];

void clear(int n) {
	for(int i=1; i<=n; i++) {
		dp[i] = 0;
		vis[i] = 0;
	}
}

void dfs(int v) {
	vis[v] = 1;
	dp[v] = s[v-1] - '0';
	int rb = -(s[v-1] - '0');
	for(int i=0; i<(int) V[v].size(); i++) {
		int u = V[v][i];
		if(!vis[u]) {
			dfs(u);
			rb += dp[u];
		}
	}
	dp[v] = max(dp[v], rb);
}

int main() {
	fastio;
	int n;
	cin>>n;
	for(int i=0; i<(n-1); i++) {
		int a, b;
		cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	cin>>s;
	int ans = 0;
	for(int i=1; i<=n; i++) {
		clear(n);
		dfs(i);
		ans = max(ans, dp[i]);
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...