제출 #1350954

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

const int MAX_N = 100'000 + 10;

int n, dp[MAX_N][2][2], ans;
vector<int> adj[MAX_N];
bitset<MAX_N> c;

void dfs(int u, int p) {
    dp[u][0][c[u]] = 0;
    dp[u][0][!c[u]] = MAX_N;
    dp[u][1][!c[u]] = 1;
    dp[u][1][c[u]] = MAX_N;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        int upd[2][2] = {{MAX_N, MAX_N}, {MAX_N, MAX_N}};
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    upd[i][j ^ k] = min(upd[i][j ^ k], dp[u][i][j] + dp[v][k][i]);
                }
            }
        }
        swap(dp[u], upd);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;

    for (int e = 1, u, v; e <= n - 1; ++e) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int u = 1; u <= n; ++u) {
        int x;
        cin >> x;
        c[u] = x;
    }

    dfs(1, -1);

    ans = min(dp[1][0][0], dp[1][1][0]);

    if (ans == MAX_N) {
        cout << "impossible\n";
    } else {
        cout << ans << '\n';
    }
}
#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...