제출 #1125699

#제출 시각아이디문제언어결과실행 시간메모리
1125699Kel_MahmutPower Plant (JOI20_power)C++20
100 / 100
183 ms29596 KiB
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for(int i = 0; i < n - 1; i++){
		int a, b; cin >> a >> b; a--, b--;
		g[a].pb(b); g[b].pb(a);
	}
	string s;
	cin >> s;

	vector<int> bos(n);
	vector<int> dolu(n);

	function<void(int, int)> dfs = [&](int u, int p){
		for(int v : g[u]){
			if(v == p) continue;
			dfs(v, u);
		}

		if(s[u] == '0'){
			int mxbos = 0;
			int herdolu = 0;
			for(int v : g[u]){
				if(v == p) continue;
				mxbos = max(mxbos, bos[v]);
				herdolu += dolu[v];
			}
			bos[u] = max(bos[u], mxbos);
			bos[u] = max(bos[u], herdolu);
			dolu[u] = max(dolu[u], herdolu);
		}
		else{
			int mxdolu = 0;
			int mxbos = 0;
			int herdolu = 0;
			for(int v : g[u]){
				if(v == p) continue;
				mxdolu = max(mxdolu, dolu[v]);
				mxbos = max(mxbos, bos[v]);
				herdolu += dolu[v];
			}
			bos[u] = max(bos[u], mxdolu + 1);
			bos[u] = max(bos[u], herdolu - 1);
			bos[u] = max(bos[u], 1);
			bos[u] = max(bos[u], mxbos);
			dolu[u] = max(dolu[u], 1);
			dolu[u] = max(dolu[u], herdolu - 1);
		}
	};

	dfs(0, 0);
	cout << bos[0] << endl;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...