Submission #1133569

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

bool used[100];
int n,x,h[100],dp[100];
vector<int> G[100];

int dfs(int v){
	used[v] = true;
	if(dp[v] >= 0) return dp[v];
	int child = 0,sum = 0;
	for(int i = 0;i < G[v].size();i++){
		if(!used[G[v][i]]){
			sum += dfs(G[v][i]);
			child++;
		}
	}
	if(v == x) return dp[v] = sum;
	if(sum == 0) return dp[v] = 0 + h[v] * 2;
	else return dp[v] = sum + 2;
}

int main(){
	cin >> n >> x; x--;
	for(int i = 0;i < n;i++) {
		cin >> h[i];
		dp[i] = -1;
	}
	h[x] = 0;
	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);
	}
	cout << dfs(x) << endl;
	return 0;
}

Submission Info

Judge Result