제출 #726630

#제출 시각아이디문제언어결과실행 시간메모리
726630mariowongPower Plant (JOI20_power)C++14
100 / 100
150 ms31620 KiB
#include <bits/stdc++.h>
using namespace std;

vector <int> edge[200005];
int ans,dp[200005];
string s;
void dfs(int x,int p){
	int sum=0,mx=0;
	for (auto id:edge[x]){
		if (id != p){
			dfs(id,x);
			sum+=dp[id];
			mx=max(mx,dp[id]);
		}
	}
	if (s[x-1] == '0'){
		dp[x]=sum;
		ans=max(ans,dp[x]);	
	}
	else {
		ans=max(ans,mx+1);	
		dp[x]=max(1,sum-1);
		ans=max(ans,dp[x]);	
	}
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i=1;i<n;i++){
    	int u,v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);	
    }
	cin >> s;
	dfs(1,-1); 
	cout << ans << "\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...