Submission #769150

#	Time	Username	Problem	Language	Result	Execution time	Memory
769150		Mohammad_Parsa	Power Plant (JOI20_power)	C++17	100 / 100	142 ms	29580 KiB

power

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=2e5+7;
int n,dp[2][N];
string s;
vector<int>vec[N];

void dfs(int v=1,int p=0){
	for(auto u:vec[v]){
		if(u==p)continue;
		dfs(u,v);
	}
	if(s[v-1]=='0'){
		for(auto u:vec[v]){
			if(u==p)continue;
			dp[0][v]+=dp[0][u];
			dp[1][v]=max(dp[1][v],dp[1][u]);
		}
	}
	else{
		int x0=-1,x1=-1,y1=0,z0=1,z1=1;
		for(auto u:vec[v]){
			if(u==p)continue;
			x0+=dp[0][u];
			x1=max(x1,dp[1][u]-1);
			y1=max(y1,dp[1][u]);
			z1=max(z1,dp[0][u]+1);
		}
		dp[0][v]=max(0,max(x0,z0));
		dp[1][v]=max(x1,max(z1,y1));
	}
}

int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	int u,v;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		vec[u].pb(v);
		vec[v].pb(u);
	}
	cin>>s;
	dfs();
	cout<<max(dp[0][1],dp[1][1]);
}

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