제출 #1255480

#제출 시각아이디문제언어결과실행 시간메모리
1255480ebrambillPower Plant (JOI20_power)C++17
100 / 100
205 ms29988 KiB
//In the name of GOD

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

#define pb push_back

const int maxN=2e5+5;
int n, dp[maxN][2];
string s;
bool pw[maxN];
vector<int> neib[maxN];

void dfs(int v, int p=0){
	int sum=0, maxi[2]={0, 0};
	for (int u: neib[v]){
		if(u!=p){
		   	dfs(u, v);
			sum+=dp[u][1];
			maxi[0]=max(maxi[0], dp[u][0]);
			maxi[1]=max(maxi[1], dp[u][1]);
		}
	}

	dp[v][0]=max(max(maxi[0], sum-pw[v]), maxi[pw[v]]+pw[v]);
	dp[v][1]=max(sum-pw[v], 0+pw[v]);
}

int main(){
	cin >>n;
	for (int i=1, u, v; i<n; i++){
		cin >>u >>v;
		neib[u].pb(v);
		neib[v].pb(u);
	}
	cin >>s;
	for (int v=1; v<=n; v++) pw[v]=(s[v-1]=='1');
	dfs(1);
	cout <<dp[1][0];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...