oj.uz

Submission #444909

# Submission time Handle Problem Language Result Execution time Memory
444909 2021-07-15T20:35:11 Z dutch Power Plant (JOI20_power) C++17
0 / 100
 3 ms 4940 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;

int n, ans, dp[MAXN];
vector<int> g[MAXN];
string s;

void dfs(int u, int p){
	if(s[u] == '1'){
		dp[u] = -1;
		for(int &v : g[u]){
			if(v == p) continue;
			dfs(v, u);
			ans = max(ans, 1 + dp[v]);
			dp[u] += dp[v];
		}
		dp[u] = max(dp[u], 1);
	}else{
		for(int &v : g[u]){
			if(v == p) continue;
			dfs(v, u);
			dp[u] += dp[v];
		}
		ans = max(ans, dp[u]);
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<n; ++i){
		int u, v; cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cin >> s;
	dfs(0, 0);
	cout << ans;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -