Submission #334922

#TimeUsernameProblemLanguageResultExecution timeMemory
334922Mo_TOI_I_am_GarbagePower Plant (JOI20_power)C++14
100 / 100
275 ms25492 KiB
#include<bits/stdc++.h>
using namespace std;
vector<int> V[200050];
string str; int a, ans = 0;
int search(int now, int from)
{
	if(str[now] == '1')
	{
		int cnt = 0, mx = 0;
		for(int x : V[now])
		{
			if(x == from) continue;
			int t = search(x, now);
			cnt += t;
			mx = max(mx, t);
		}
		ans = max(ans, max(mx + 1, cnt - 1));
		return max(1, cnt - 1);
	}
	else
	{
		int cnt = 0;
		for(int x : V[now])
		{
			if(x == from) continue;
			cnt += search(x, now);
		}
		ans = max(ans, cnt);
		return cnt;
	}
}
int main()
{
	cin >> a;
	for(int i=0; i < a - 1; i ++)
	{
		int x, y; cin >> x >> y;
		x --; y --;
		V[x].push_back(y);
		V[y].push_back(x);
	}
	cin >> str;
	search(0, -1);
	cout << ans << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...