Submission #763312

#	Time	Username	Problem	Language	Result	Execution time	Memory
763312		vjudge1	Power Plant (JOI20_power)	C++17	47 / 100	4 ms	5076 KiB

power

#include<bits/stdc++.h>
using namespace std;

int n, x, y, ans = 0, dp[100001];
vector<int> vec[100001];
string s;
bool visited[100001];

void dfs(int x)
{
	int maxi = 0;
	visited[x] = true;
	for(int c : vec[x])
	{
		if(!visited[c])
		{
			dfs(c);
			dp[x] += dp[c];
			maxi = max(dp[c], maxi);
		}
	}
	dp[x] = max(s[x - 1] - '0', dp[x] - s[x - 1] + '0');
	ans = max(ans, max(maxi + s[x - 1] - '0', dp[x]));
}

int main()
{
	cin >> n;
	for(int i = 1; i < n; ++i)
	{
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	cin >> s;
	dfs(n);
	cout << ans;
}

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