Submission #311836

#TimeUsernameProblemLanguageResultExecution timeMemory
311836sofapudenPower Plant (JOI20_power)C++14
100 / 100
392 ms25864 KiB
#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";
}
	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...