Submission #520869

#	Time	Username	Problem	Language	Result	Execution time	Memory
520869		new_acc	Power Plant (JOI20_power)	C++14	100 / 100	163 ms	32840 KiB

power

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=2e5+10;
int dp[N][2],t[N];
vi graf[N];
void dfs(int v,int o){
	int xd=0,xd2=0,xd3=0;
	for(auto u:graf[v]){
		if(u==o) continue;
		dfs(u,v);
		xd=max(xd,dp[u][0]);
		xd2=max(xd2,dp[u][1]);
		xd3+=dp[u][1];
	}
	if(t[v]) dp[v][0]=max({xd3-1,xd,xd2+1,1}),dp[v][1]=max({1,xd3-1});
	else dp[v][0]=max({xd3,xd,0}),dp[v][1]=xd3;
}
void solve(){
	int n;
	cin>>n;
	rep(i,n-1){
		int a,b;
		cin>>a>>b;
		graf[a].push_back(b),graf[b].push_back(a);
	}
	rep(i,n){
		char a;
		cin>>a;
		t[i+1]=int(a)-48;
	}
	dfs(1,1);
	cout<<dp[1][0]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

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