Submission #868752

#	Time	Username	Problem	Language	Result	Execution time	Memory
868752		rorro	Power Plant (JOI20_power)	C++17	100 / 100	122 ms	42128 KiB

power

#include <bits/stdc++.h>

#define ll long long
#define lld long double
#define fi first
#define se second
#define mp make_pair
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define pb push_back
#define eb emplace_back
#define remax(a, b) a = max(a, b);
#define remin(a, b) a = min(a, b);
#define all(x) x.begin(), x.end()
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bit(n, x) (n & (1 << x))

using namespace std;
int ans = 0;
const int maxn=2e5+1;
vvi edges(maxn);
vvi dp(maxn, vi(2, 0));
string s;

void dfs(int cur, int par) {
	int sm0=0, sm1=0, mx0=0, mx1=0;
	for (int next : edges[cur]) {
		if (next != par) {
			dfs(next, cur);
			sm0 += max(0, dp[next][0]);
			sm1 += max(0, dp[next][1]);
			remax(mx0, dp[next][0]);
			remax(mx1, dp[next][1]);
		}
	}
	if (s[cur] == '1') { //if there is
		dp[cur][1] = max({1, sm1-1}); 
		dp[cur][0] = max({1, sm1-1, mx0, mx1+1}); 
	} else {
		dp[cur][1] = max({sm1});
		dp[cur][0] = max({sm1, mx0});
	}
	//remax(ans, dp[cur][0]);
}

int main() {
	fastio();
	int n;
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a;--b;
		edges[a].eb(b);
		edges[b].eb(a);
	}
	cin >> s;
	dfs(0, -1);
	/*for (int i = 0; i < n; ++i) {
		cout << i+1 << ' ' << dp[i][0] << ' ' << dp[i][1] << endl;
	}*/
	cout << dp[0][0] << '\n';
    return 0;
}

/* --3
6
2 3
4 3
1 3
3 5
6 2
110011
*/

/* --3
8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111
*/

/* --5
16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110
*/

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