結果
問題 | No.2205 Lights Out on Christmas Tree |
ユーザー |
![]() |
提出日時 | 2023-02-03 21:43:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 874 bytes |
コンパイル時間 | 1,906 ms |
コンパイル使用メモリ | 198,196 KB |
最終ジャッジ日時 | 2025-02-10 09:00:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;int inf = 1001001001;int dp[200200][2];void dfs(int n,int p,vector<int>&c,vector<vector<int>>&ki) {dp[n][1-c[n]] = inf;for(int i:ki[n]) {if(i == p) {continue;}dfs(i,n,c,ki);int a = dp[n][0],b = dp[n][1];dp[n][0] = min({inf,dp[i][0]+b+1,dp[i][1]+a});dp[n][1] = min({inf,dp[i][0]+a+1,dp[i][1]+b});}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<vector<int>>ki(N);for(int i = 0; i < N-1; i++) {int a,b;cin >> a >> b;a--;b--;ki[a].push_back(b);ki[b].push_back(a);}vector<int>c(N);for(int i = 0; i < N; i++) {cin >> c[i];}dfs(0,-1,c,ki);cout << ((dp[0][1] == inf)?-1:dp[0][1]) << endl;}