Submission #334922

#	Time	Username	Problem	Language	Result	Execution time	Memory
334922		Mo_TOI_I_am_Garbage	Power Plant (JOI20_power)	C++14	100 / 100	275 ms	25492 KiB

power

#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;
}

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