제출 #1255452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255452		Seyyed_Mojtaba_Mortazavi	Power Plant (JOI20_power)	C++20	47 / 100	1595 ms	19412 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;

int dp[MAXN];
bool mark[MAXN];
vector <int> e[MAXN];

void dfs(int v, int par = -1)
{
	int sum = 0;
	for (auto u : e[v])
	{
		if (u != par)
		{
			dfs(u, v);
			sum += dp[u];
		}
	}
	dp[v] = max((int) mark[v], sum - mark[v]);
}

signed main()
{
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int v, u;
		cin >> v >> u;
		e[v].push_back(u);
		e[u].push_back(v);
	}
	for (int i = 1; i <= n; i++)
	{
		char c;
		cin >> c;
		mark[i] = (c == '1');
	}
	for (int i = 1; i <= n; i++)
	{
		if (mark[i])
		{
			dfs(i);
			for (auto u : e[i])
				ans = max(ans, dp[u] + 1);
			ans = max(ans, dp[i]);
		}
	}
	cout << ans << endl;
}

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