Submission #726630

#	Time	Username	Problem	Language	Result	Execution time	Memory
726630		mariowong	Power Plant (JOI20_power)	C++14	100 / 100	150 ms	31620 KiB

power

#include <bits/stdc++.h>
using namespace std;

vector <int> edge[200005];
int ans,dp[200005];
string s;
void dfs(int x,int p){
	int sum=0,mx=0;
	for (auto id:edge[x]){
		if (id != p){
			dfs(id,x);
			sum+=dp[id];
			mx=max(mx,dp[id]);
		}
	}
	if (s[x-1] == '0'){
		dp[x]=sum;
		ans=max(ans,dp[x]);	
	}
	else {
		ans=max(ans,mx+1);	
		dp[x]=max(1,sum-1);
		ans=max(ans,dp[x]);	
	}
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i=1;i<n;i++){
    	int u,v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);	
    }
	cin >> s;
	dfs(1,-1); 
	cout << ans << "\n";
	return 0;
}

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