Submission #750609

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int search(int cur, int h[], vector<int> edges[], int min_costs[], int parent = -1) {
  int &cost = min_costs[cur];
  if (cost < 0) {
    cost = 0;
    for (size_t ei = 0; ei < edges[cur].size(); ++ei) {
      int next = edges[cur][ei];
      if (next != parent) {
        int child_cost = search(next, h, edges, min_costs, cur);
        if (child_cost > 0 or h[next]) {
          cost += child_cost + 2;
        }
      }
    }
  }
  return cost;
}

int main() {
  int n, x, a, b;
  int h[100], min_costs[100];
  vector<int> edges[100];
  cin >> n >> x;
  for (int ni = 0; ni < n; ++ni) {
    cin >> h[ni];
  }
  for (int ni = 0; ni < n - 1; ++ni) {
    cin >> a >> b;
    edges[a - 1].push_back(b - 1);
    edges[b - 1].push_back(a - 1);
  }
  fill(min_costs, min_costs + n, -1);
  cout << search(x - 1, h, edges, min_costs) << endl;
  return 0;
}

Submission Info

Judge Result