結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー |
|
提出日時 | 2023-02-03 22:02:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 1,087 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 174,520 KB |
実行使用メモリ | 41,472 KB |
最終ジャッジ日時 | 2024-07-02 19:57:37 |
合計ジャッジ時間 | 6,329 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(false);cin.tie(0);int n, u, v;cin >> n;vector<vector<int>> g(n);vector<int> c(n), wv;for(int i = 1; i < n; i++){cin >> u >> v;g[--u].push_back(--v);g[v].push_back(u);}for(int i = 0; i < n; i++){cin >> c[i];if(c[i] == 0)wv.push_back(i);}if(wv.size() & 1){cout << -1 << '\n';return 0;}vector<vector<int>> dp(n, vector<int>(2, 1 << 29));function<void(int,int)> dfs = [&](int v, int p){vector<int>& temp = dp[v];temp[c[v] ^ 1] = 0;for(auto &&u:g[v]){if(u == p)continue;dfs(u, v);vector<int> nxt(2, 1 << 30);for(int i = 0; i < 2; i++){for(int j = 0; j < 2; j++){nxt[i ^ j] = min(nxt[i ^ j], temp[i] + dp[u][j] + j);}}swap(temp, nxt);}};dfs(0, -1);cout << dp[0][0] << '\n';}