Submission #365158

#	Time	Username	Problem	Language	Result	Execution time	Memory
365158		ronnith	Power Plant (JOI20_power)	C++14	0 / 100	5 ms	4972 KiB

power

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200000;

int n;
ll dp[N][3];
string s;
vector<int> adj[N];

void dfs(int x, int pr) {

	dp[x][0] = INT_MIN;
	if(s[x] == '1') 
		dp[x][0] = 1;

	ll val1 = INT_MIN, val2 = 0, val3 = 0;
	if(s[x] == '1') 
		val1 = 1;

	ll v2 = 0;

	for(auto e : adj[x]) if(e != pr) {
		dfs(e, x);
		if(dp[x][0] != INT_MIN)
			dp[x][0] = 1 + max(dp[x][0] - 1, dp[e][2]);
		val2 += max(0LL, dp[e][1]);
		v2 += max(0LL, dp[e][2]);
		val3 = max(val3, dp[e][1]);
	}

	dp[x][1] = max(val1, val2 - (s[x] == '1'));
	dp[x][1] = max(dp[x][1], val3);

	dp[x][2] = val1;
	dp[x][2] = max(dp[x][2], v2 - (s[x] == '1'));
	dp[x][2] = max(dp[x][2], 0LL);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for(int i = 0;i < n-1;i ++) {
		int x, y; cin >> x >> y;
		x --,y --;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	cin >> s;

	dfs(0, -1);

	ll ans = 0;
	for(int i = 0;i < n;i ++) {
//		cerr << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << '\n';
		ans = max(ans, dp[i][0]);
		ans = max(ans, dp[i][1]);
	}

	cout << ans << '\n';

}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53