제출 #1255436

#제출 시각아이디문제언어결과실행 시간메모리
1255436arashmemarPower Plant (JOI20_power)C++20
100 / 100
128 ms27124 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100;

int dp[2][maxn];

vector <int> ne[maxn];
bool mark[maxn];
string str;

void dfs(int v)
{
	if (str[v - 1] == '1')
	{
		dp[1][v] = dp[0][v] = 1;
	}
	mark[v] = 1;
	int s = 0;
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		dfs(u);
		s += dp[1][u];
		dp[0][v] = max(dp[0][v], max(dp[0][u], dp[1][u] + (str[v - 1] == '1')));
	}
	dp[1][v] = max(dp[1][v], s - (str[v - 1] == '1'));
	dp[0][v] = max(dp[0][v], s - (str[v - 1] == '1'));
	return ;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1;i < n;i++)
	{
		int v, u;
		cin >> v >> u;
		ne[v].push_back(u);
		ne[u].push_back(v);
	}
	cin >> str;
	dfs(1);

	cout << dp[0][1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...