Submission #286922

---

Source Code Expand

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vertex;
typedef vector<vertex> graph;
int n, x;
int h[100];
bool used[100];
graph g, f;

int dfs(int u){
	used[u] = true;
	int res = 0;
	for(int v: g[u]){
		if(used[v]) continue;
		res += dfs(v);
	}
	if(res||h[u]) res += 2;
	return res;
}

int main(){
	cin>>n>>x;
	x--;
	g = graph(n);
	f = graph(n);
	for(int i = 0; i < n; i++) cin>>h[i];
	h[x] = 0;
	for(int i = 0; i < n-1; i++){
		int a, b;
		cin>>a>>b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	int res = dfs(x);
	if(res) res-=2;
	/*
	used[x] = true;
	int mx = 0;
	for(int i = 1; !f[x].empty(); i++){
		x = f[x][0];
		int r = dfs(x);
		used[x] = true;
		if(r){
			res += r-2;
			mx = i;
		}
	}
	res += 2*mx;
	*/
	cout<<res<<endl;
	return 0;
}

Submission Info

Judge Result