Submission #286815

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <fstream>
#include <string>
#include <functional>

using namespace std;

int dfs(vector< vector<int> > &G, vector<int> &h, vector<bool> &visit, int pos, int &root){
	visit[pos] = true;

	bool valid = false;
	
	int ret = 0;
	for(int i=0; i<G[pos].size(); i++){
		if(visit[ G[pos][i] ]) continue;
		int tmp = dfs(G, h, visit, G[pos][i], root);
		
		ret += tmp;
		
		if(tmp>0) valid = true;
	}
	if(h[pos] > 0) valid = true;
	if(valid && pos != root) ret += 2;
	return ret;
}


int main(){
	int n, x;
	cin >> n >> x;
	vector<int> h(n);
	for(int i=0; i<n; i++) cin >> h[i];
	vector< vector<int> > G(n);
	for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	int ans = 1e9;
	//root
	for(int i=0; i<n; i++){
		vector<bool> visit(n, false);
		ans = min(ans, dfs(G,h,visit, i, i));
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result