제출 #1029363

#제출 시각아이디문제언어결과실행 시간메모리
1029363MDarioThe Xana coup (BOI21_xanadu)C++17
100 / 100
36 ms17236 KiB
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
typedef long long ll;
typedef pair<pair<ll, ll>, pair<ll, ll>> Ans;

const string noyes[2] = {"NO", "YES"};
const ll INFLL = (1ll << 62);
const int INF = (1 << 30);
const int MAXN = 100'001;
const ll MOD = 1'000'000'007;

vector<int> g[MAXN];
int a[MAXN];

Ans f(int x, int ax) {
  // Valor inicial dependiendo de si este nodo estaba o no encendido
  // inicialmente
  Ans y = {{INF, 1}, {0, INF}};
  if (a[x])
    y = {{0, INF}, {INF, 1}};
  for (int i : g[x]) {
    if (i != ax) {
      // temporal y
      Ans ty = f(i, x);
      y = {{min(y.F.F + ty.S.F, y.S.F + ty.S.S),
            min(y.F.S + ty.F.F, y.S.S + ty.F.S)},
           {min(y.S.F + ty.S.F, y.F.F + ty.S.S),
            min(y.S.S + ty.F.F, y.F.S + ty.F.S)}};
    }
  }
  return y;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;

  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++)
    cin >> a[i];

  Ans ans = f(1, 0);
  ll final_ans = min(ans.S.F, ans.S.S);
  if (final_ans > n)
    cout << "impossible\n";
  else
    cout << min(ans.S.F, ans.S.S) << "\n";

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...