Submission #434927

#TimeUsernameProblemLanguageResultExecution timeMemory
434927xuliuPower Plant (JOI20_power)C++14
47 / 100
1582 ms15420 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, int root) {
	vis[v] = 1;
	dp[v] = s[v-1] - '0';
	int rb = 0, rc = 0;
	for(int i=0; i<(int) V[v].size(); i++) {
		int u = V[v][i];
		if(!vis[u]) {
			dfs(u, root);
			rb += dp[u];
			rc = max(rc, dp[u]);
		}
	}
	if(v == root)
		dp[v] = rc + 1;
	else {
		rb -= s[v-1] - '0';
		dp[v] = max(dp[v], rb);
	}
	debug cerr<<"dp["<<v<<"] = "<<dp[v]<<"\n";
}

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++) {
		if(s[i-1] == '1') {
			clear(n);
			dfs(i, 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...