Submission #951804

#TimeUsernameProblemLanguageResultExecution timeMemory
951804dio_2Power Plant (JOI20_power)C++17
0 / 100
2 ms5724 KiB
#include<bits/stdc++.h>
using namespace std;

const int nax = (int)2e5 + 10;
bool isGen[nax];
vector<int> g[nax];
int ans;
int dp[nax];

void dfs(int u, int par){
	if(isGen[u]){
		int best = 0;
		for(int v : g[u]) if(v != par){
			dfs(v, u);
			dp[u] += dp[v];
			best = max(best, dp[v] + 1); // use the Generator on v.
		}
		ans = max(ans, best);
		dp[u]--; // because i have generator and it will break
		dp[u] = max(dp[u], 1); // it will break only if i have > 2.
	} else {
		for(int v : g[u]) if(v != par){
			dfs(v, u);
			dp[u] += dp[v];
		}
		ans = max(ans, dp[u]);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	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);
	}
	
	for(int i = 1;i <= n;i++){
		char c; cin >> c;
		if(c == '1') isGen[i] = 1;
	}
	
	dfs(1, -1);
	
	cout << ans << '\n';
	
	return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...