Submission #1255452

#TimeUsernameProblemLanguageResultExecution timeMemory
1255452Seyyed_Mojtaba_MortazaviPower Plant (JOI20_power)C++20
47 / 100
1595 ms19412 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...