Submission #769150

#TimeUsernameProblemLanguageResultExecution timeMemory
769150Mohammad_ParsaPower Plant (JOI20_power)C++17
100 / 100
142 ms29580 KiB
/* 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]);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...