Submission #541398

#	Time	Username	Problem	Language	Result	Execution time	Memory
541398		xuliu	Power Plant (JOI20_power)	C++17	100 / 100	165 ms	33184 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

/*
ans: dp[1][0]
dp[v][1] = max(a[v], sum(dp[u][1])-a[v]), for u := child of v
dp[v][0] =  max(sum(dp[u][1])-a[v], max(dp[u][1])+a[v], max(dp[u][0]))
*/

const int N = 2e5 + 4;
vector<int> V[N];
int dp[N][2], a[N];

void dfs(int v, int p=0) {
	int max0 = 0, max1 = 0, sum = 0;
	for(int u : V[v]) {
		if(u != p) {
			dfs(u, v);
			max0 = max(max0, dp[u][0]);
			max1 = max(max1, dp[u][1]);
			sum += dp[u][1];
		}
	}
	dp[v][0] = max(sum-a[v], max(max1+a[v], max0));
	dp[v][1] = max(a[v], sum-a[v]);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0; i<(n-1); i++) {
		int a, b; cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	string s; cin>>s;
	for(int i=1; i<=n; i++) a[i] = (s[i-1] - '0');
	dfs(1);
	cout<<dp[1][0];
}

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