Submission #1255480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255480		ebrambill	Power Plant (JOI20_power)	C++17	100 / 100	205 ms	29988 KiB

power

//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];
}

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