이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
#define ll long long
#define x first
#define y second
#define MOD 1000000007
vector<vector<int>> graph;
vector<int> S;
vector<vector<vector<ll>>> dp;
int N;
ll inf = 1e9+5;
void dfs(int n, int p){
if((int)graph[n].size() == 1 && n != 0){
if(S[n]){
dp[n][0][0] = inf;
dp[n][0][1] = 1;
dp[n][1][0] = 0;
dp[n][1][1] = inf;
}
if(!S[n]){
dp[n][0][0] = 0;
dp[n][0][1] = inf;
dp[n][1][0] = inf;
dp[n][1][1] = 1;
}
return;
}
ll dp1[2][2];
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
dp1[i][j] = i == 0 ? 0 : inf;
}
}
for(int a : graph[n]){
if(a == p) continue;
dfs(a, n);
}
int i = 0;
for(int a : graph[n]){
if(a == p) continue;
// numero pari di 1
ll new_0_0;
ll new_1_0;
ll new_0_1;
ll new_1_1;
if(!i)
new_0_0 = min(inf, dp[a][0][0]);
else
new_0_0 = min(dp1[1][0] + dp[a][0][1], dp1[0][0] + dp[a][0][0]);
// numero dispari di 1
new_1_0 = min(dp1[0][0] + dp[a][0][1], dp1[1][0] + dp[a][0][0]);
if(!i)
new_0_1 = min(inf, dp[a][1][0]);
else
new_0_1 = min(dp1[1][1] + dp[a][1][1], dp1[0][1] + dp[a][1][0]);
// numero dispari di 1
new_1_1 = min(dp1[0][1] + dp[a][1][1], dp1[1][1] + dp[a][1][0]);
dp1[0][0] = new_0_0;
dp1[1][0] = new_1_0;
dp1[0][1] = new_0_1;
dp1[1][1] = new_1_1;
i++;
}
ll min_o_off = dp1[1][0];
ll min_e_off = dp1[0][0];
ll min_o_on = dp1[1][1];
ll min_e_on = dp1[0][1];
// cout<<"DEBUG-->"<<min_o_off<<" "<<min_e_off<<" "<<min_o_on<<" "<<min_e_on<<endl;
if(S[n]){
dp[n][0][0] = min_o_off; // tutti i figli devono essere spenti e devo usare min_o
dp[n][0][1] = min_e_on+1;
dp[n][1][0] = min_e_off;
dp[n][1][1] = min_o_on+1;
}
if(!S[n]){
dp[n][0][0] = min_e_off; // tutti i figli devono essere spenti e devo usare min_o
dp[n][0][1] = min_o_on+1;
dp[n][1][0] = min_o_off;
dp[n][1][1] = min_e_on+1;
}
}
void solve(){
// ifstream in("input.txt");
// ofstream out("output.txt");
cin>>N;
graph.assign(N, vector<int>());
dp.assign(N, vector<vector<ll>>(2, vector<ll>(2, inf)));
S.assign(N, false);
for(int i = 0; i < N-1; i++){
int a, b;
cin>>a>>b;
a--, b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
for(int i = 0; i < N; i++)
cin>>S[i];
dfs(0, -1);
ll ans = min(dp[0][0][0], dp[0][0][1]);
if(ans >= inf) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |