Submission #1281102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281102		WH8	Power Plant (JOI20_power)	C++20	100 / 100	161 ms	30992 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double


signed main(){
	int n;cin>>n;
	vector<vector<int>> al(n+1);
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		al[a].pb(b);
		al[b].pb(a);
	}
	vector<bool> s(n+1);
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='1')s[i]=1;
		else s[i]=0;
	}
	vector<int> dp(n+1, 0);
	auto dfs=[&](auto && dfs, int x, int p)->void{
		int sm=0;
		for(auto it:al[x]){
			if(it==p)continue;
			dfs(dfs,it,x);
			sm+=dp[it];
		}
		if(s[x])dp[x]=max(1ll, sm-1);
		else dp[x]=sm;
	};
	dfs(dfs, 1, 0);
	vector<int> res(n+1, 0);
	auto reroot=[&](auto && reroot, int x, int p, int pv)->void{
		int sm=pv;
		for(auto it:al[x]){
			if(it==p)continue;
			sm+=dp[it];
		}
		if(s[x])res[x]=max(pv+1, sm-1);
		else res[x]=sm;
		for(auto it:al[x]){
			if(it==p)continue;
			if(s[x])reroot(reroot, it, x, max(1ll, sm-dp[it]-1));
			else reroot(reroot, it, x, sm-dp[it]);
		}
	};
	reroot(reroot, 1, 0, 0);
	cout<<*max_element(res.begin(),res.end());
}
/*
3
1 2
2 3
111
*/

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