Submission #651816

#	Time	Username	Problem	Language	Result	Execution time	Memory
651816		beaconmc	Power Plant (JOI20_power)	C++14	100 / 100	347 ms	28648 KiB

power

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)


#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
ll n;
string sus;
vector<ll> edges[200001];
ll par[200001];
bool visited[200001];
ll dps[200001];
ll ans = 0;

void dfs(ll a){
	for (auto&i : edges[a]){
		if (!visited[i]){
			visited[i] = true;
			par[i] = a;
			dfs(i);
		}
	}
}

ll dp(ll a){


	if (dps[a] != -1) return dps[a];
	ll sum = 0;
	ll maxi = 0;

	for (auto&i : edges[a]){
		if (i==par[a]) continue;
		sum += dp(i);
		maxi = max(maxi, dp(i));
	}
	if (sus[a-1] == '1'){
		ans = max(ans, max(maxi+1, sum-1));
	}else{
		ans = max(ans, sum);
	}
	dps[a] = max(sum - sus[a-1] + '0', ll(sus[a-1] - '0'));
	return max(sum - sus[a-1] + '0', ll(sus[a-1] - '0'));
}

int main(){
	
	cin >> n;
	if (n==1){
		cout << 1;
		return 0;
	}

	FOR(i,0,n-1){
		ll a,b;
		cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	cin >> sus;
	FOR(i,0,n+1) par[i] = -1, visited[i] = 0, dps[i] = -1;
	visited[1] = true;
	dfs(1);


	dp(1);
	cout << ans;





}

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