Submission #1256390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256390		namhh	Power Plant (JOI20_power)	C++20	0 / 100	3 ms	4936 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int base = 4e3;
int n,dp[N][2],val[N];
string s;
vector<int>adj[N];
void dfs(int u, int p){
	if(adj[u].size() == 1 && u != 1) dp[u][0] = dp[u][1] = val[u];
	int sum = 0;
	for(int v: adj[u]){
		if(v != p){
			dfs(v,u);
			dp[u][0] = max(dp[u][0],dp[v][1]+val[u]);
			dp[u][1] += dp[v][1];
		}
	}
	dp[u][1] -= val[u];
	dp[u][1] = max(dp[u][1],val[u]);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i < n; i++){
    	int u,v;
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
	}
	cin >> s;
	for(int i = 0; i < n; i++) val[i+1] = s[i]-'0';
	dfs(1,0);
//	for(int i = 1; i <= n; i++){
//		for(int j = 0; j <= 1; j++) cout << i << " " << j << " " << dp[i][j] << "\n";
//	}
	cout << max(dp[1][0],dp[1][1]);
}

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