제출 #1327599

#제출 시각아이디문제언어결과실행 시간메모리
1327599vtnooPower Plant (JOI20_power)C++20
0 / 100
2 ms1080 KiB
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int MAXN=2e5+5,INF=1e9;
vector<int>adj[MAXN];
int dp[MAXN],gen[MAXN];
void chmax(int &a,int b){
	a=max(a,b);
}
int f(int u,int p){
	int &ret=dp[u];
	int exstOn=0;
	for(auto v:adj[u]){
		if(v==p)continue;
		int ndp=f(v,u);
		exstOn+=ndp;
	}
	if(p==-1){
		chmax(ret,exstOn);
	}else{
		chmax(ret,max(gen[u],exstOn-gen[u]));
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;cin>>n;
	L(i,0,n-2){
		int a,b;cin>>a>>b;
		a--;b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	string s;cin>>s;
	L(i,0,n-1)if(s[i]=='1')gen[i]=1;
	int ans=0;
	L(i,0,n-1){
		if(!gen[i])continue;
		memset(dp,0,sizeof(dp));
		chmax(ans,f(i,-1));
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...