Submission #732741

#	Time	Username	Problem	Language	Result	Execution time	Memory
732741		myrcella	Power Plant (JOI20_power)	C++17	100 / 100	202 ms	32448 KiB

power

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

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;

int n;
vector <int> edge[maxn];
bool mark[maxn];
int dp[maxn][2];

void dfs(int u,int fa) {
	int sum = 0,mx1 = -maxn,mx0 = -maxn;
	for (int v:edge[u]) {
		if (v==fa) continue;
		dfs(v,u);
		sum += dp[v][0];
		mx1 = max(mx1,dp[v][1]);
		mx0 = max(mx0,dp[v][0]);
	}
	if (mark[u]) {
		dp[u][0] = max(sum-1,1);
		dp[u][1] = max(mx1,mx0+1);
		dp[u][1] = max(dp[u][1],sum-1);
	}
	else {
		dp[u][0] = sum;
		dp[u][1] = mx1;
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	rep(i,1,n) {
		int u,v;cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	string s;cin>>s;
	rep(i,0,n) if (s[i]=='1') mark[i+1]=1;
	dfs(1,-1);
	cout<<max(dp[1][0],dp[1][1]);
	return 0;
}

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