Submission #1301082

#TimeUsernameProblemLanguageResultExecution timeMemory
1301082witek_cppPower Plant (JOI20_power)C++20
100 / 100
113 ms30968 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define int ll
#define DUZO 1000000000000000000
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;

vvi g;
vi on;
vi dp;

int wnk = 0;

void dfs_dp(int v, int p) {
	for (int u: g[v]) {
		if (u == p) continue;
		dfs_dp(u, v);
	}
	if (on[v]) {
		dp[v] = 1; 
		int kand = -1;
		for (int u: g[v]) {
			if (u == p) continue;
			kand += dp[u];
		}
		wnk = max(wnk, kand);
		dp[v] = max(dp[v], kand);
		kand =0;
		for (int u: g[v]) {
			if (u == p) continue;
			kand = max(kand, dp[u]);
		}
		wnk = max(wnk, 1 + kand);
		
	} else {
		for (int u: g[v]) {
			if (u == p) continue;
			dp[v] += dp[u];
		}
		wnk = max(wnk, dp[v]);
	}
}

void solve() {
	int n;
	cin >> n;
	g.resize(n + 1);
	f(i, 1, n) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	on.resize(n + 1);
	f(i, 1, n + 1) {
		char c;
		cin >> c;
		on[i] = c - '0';
	}
	dp.resize(n + 1);
	dfs_dp(1, 0);
	cout << wnk << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...