제출 #311836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311836		sofapuden	Power Plant (JOI20_power)	C++14	100 / 100	392 ms	25864 KiB

power

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> gra;
string s;int n;

pair<int,int> dfs(int x, int p){
	int boff = (s[x] == '1'), bon = (s[x] == '1');
	int su = 0;
	for(auto i : gra[x]){
		if(i == p)continue;
		auto now = dfs(i,x);
		boff = max({boff,now.first,now.second+(s[x] == '1')});
		su+=now.second;
	}
	bon = max(bon,su-(s[x] == '1'));
	boff = max(boff,bon);
	return {boff,bon};
}
	

int main(){
	cin >> n;
	gra.resize(n);
	for(int i = 0; i < n-1; ++i){
		int a, b; cin >> a >> b;
		a--; b--;
		gra[a].push_back(b);
		gra[b].push_back(a);
	}
	cin >> s;
	cout << dfs(0,0).first << "\n";
}
	

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