Submission #286718

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <climits>
#include <set>
using namespace std;
#define repn(i,s,n) for (int i=int(s); i < int(n); i++)
#define rep(i,n) repn(i,0,n)
#define repd(i,n) for (int i=int(n)-1; i >= 0; i--)
typedef vector<int> VI;
typedef vector<VI> VVI;

int n, x;

VVI edges;
VI h;

// ここ以下の歩数をかえす
int dfs(int v, int p) {
  int ret = 0;
  bool hasTakara = !!h[v];
  rep(ei, edges[v].size()) {
    int u = edges[v][ei];
    if (u != p) {
      int retu = dfs(u, v);
      if (retu != -1) {
        hasTakara = true;
        ret += retu + 2;  // 行って帰ってくる
      }
    }
  }
  return hasTakara ? ret : -1;
}

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> x;
  x--;
  edges = VVI(n);
  h = VI(n);
  rep(i,n) cin >> h[i];
  rep(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  int ans = dfs(x, -1);
  cout << (ans >= 0 ? ans : 0) << endl;

  return 0;
}

Submission Info

Judge Result