Submission #763276

#	Time	Username	Problem	Language	Result	Execution time	Memory
763276		nhphan0505	Power Plant (JOI20_power)	C++17	100 / 100	129 ms	30080 KiB

power

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n, u, v, cnt[N], dp[N], ans;
bool plant[N], visited[N];
char c;
vector<vector<ll>> adj;

void dfs(ll u){
	visited[u]=1;
	ll mx=0, ct=0, pos=0;
	for(auto v:adj[u]){
		if(!visited[v]){ 
			dfs(v);
			cnt[u]+=cnt[v];
			mx=max(mx, cnt[v]);
			if(cnt[v]) ++ct, pos=v;
		}
	}
	if(plant[u]) dp[u]=mx+1;
	if(ct>1) dp[u]=max(dp[u], cnt[u]-plant[u]);
	else dp[u]=max(dp[u], dp[pos]);
	cnt[u]=max(cnt[u]-plant[u], 1LL*plant[u]);
	// cout<<u<<" "<<dp[u]<<" "<<cnt[u]<<endl;
	ans=max(ans, dp[u]);
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>n;
	adj.assign(n+1, {});
	for(ll i=1; i<n; ++i){
		cin>>u>>v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	for(ll i=1; i<=n; ++i){
		cin>>c;
		plant[i]=c-'0';
		// if(plant[i]) cout<<i<<" ";
	}
	// cout<<endl;
	dfs(1);
	cout<<ans;
    return 0;
}

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