제출 #869768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869768		serifefedartar	Power Plant (JOI20_power)	C++17	100 / 100	111 ms	30212 KiB

power

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 30; 
const ll MAXN = 2e5 + 100;
const ll MULT = 1e9;

vector<vector<int>> graph;
int here[MAXN], sub[MAXN], par[MAXN];
int ans = 0;

void dfs(int node, int parent) {
	int sum = 0;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs(u, node);
		sum += sub[u];
	}
	sub[node] = max(here[node], sum - here[node]);
}

void dfs2(int node, int parent) {
	int sum = 0;
	for (auto u : graph[node]) {
		if (u != parent)
			sum += sub[u];
	}
	sum += par[node];

	for (auto u : graph[node]) {
		if (u != parent)
			par[u] = max(here[node], sum - sub[u] - here[node]);
	}

	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs2(u, node);
	}
}

int main() {
	fast
	int N, A, B;
	cin >> N;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i < N; i++) {
		cin >> A >> B;
		graph[A].push_back(B);
		graph[B].push_back(A);
	}
	for (int i = 1; i <= N; i++) {
		char ch; cin >> ch;
		here[i] = ch - '0';
	}
	dfs(1, 1);
	dfs2(1, -1);

	for (int i = 1; i <= N; i++)
		ans = max(ans, sub[i] + par[i]);
	cout << ans << "\n";
}

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