이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=1e5+5;
int n;
int col[maxn];
ll dp[maxn][2][2];
vector<int>E[maxn];
void dfs(int nd,int pr){
if((int)E[nd].size() == 1 and E[nd][0] == pr){
if(!col[nd]){
dp[nd][0][0] = 0;
dp[nd][0][1] = 1e9;
dp[nd][1][0] = 1e9;
dp[nd][1][1] = 1;
}
else {
dp[nd][1][0] = 0;
dp[nd][1][1] = 1e9;
dp[nd][0][0] = 1e9;
dp[nd][0][1] = 1;
}
return;
}
for(auto i : E[nd]) if(i != pr) dfs(i,nd);
if(!col[nd]){
ll bef[2]; bef[0] = 0,bef[1] = 1e9;
for(auto i : E[nd]) if(i != pr){
ll now[2];
now[0] = min(bef[0] + dp[i][0][0],bef[1] + dp[i][0][1]);
now[1] = min(bef[0] + dp[i][0][1],bef[1] + dp[i][0][0]);
bef[0] = now[0];
bef[1] = now[1];
}
dp[nd][0][0] = bef[0];
dp[nd][1][0] = bef[1];
bef[0] = 0,bef[1] = 1e9;
for(auto i : E[nd]) if(i != pr){
ll now[2];
now[0] = min(bef[0] + dp[i][1][0],bef[1] + dp[i][1][1]);
now[1] = min(bef[0] + dp[i][1][1],bef[1] + dp[i][1][0]);
bef[0] = now[0];
bef[1] = now[1];
}
dp[nd][0][1] = bef[1] + 1;
dp[nd][1][1] = bef[0] + 1;
}
else {
ll bef[2]; bef[0] = 0,bef[1] = 1e9;
for(auto i : E[nd]) if(i != pr){
ll now[2];
now[0] = min(bef[0] + dp[i][0][0],bef[1] + dp[i][0][1]);
now[1] = min(bef[0] + dp[i][0][1],bef[1] + dp[i][0][0]);
bef[0] = now[0];
bef[1] = now[1];
}
dp[nd][0][0] = bef[1];
dp[nd][1][0] = bef[0];
bef[0] = 0,bef[1] = 1e9;
for(auto i : E[nd]) if(i != pr){
ll now[2];
now[0] = min(bef[0] + dp[i][1][0],bef[1] + dp[i][1][1]);
now[1] = min(bef[0] + dp[i][1][1],bef[1] + dp[i][1][0]);
bef[0] = now[0];
bef[1] = now[1];
}
dp[nd][0][1] = bef[0] + 1;
dp[nd][1][1] = bef[1] + 1;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++) for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) dp[i][j][k] = 1e9;
for(int i = 1;i < n;i++){
int x,y; cin >> x >> y;
E[x].push_back(y);
E[y].push_back(x);
}
for(int i = 1;i <= n;i++) cin >> col[i];
dfs(1,0);
// for(int i = 1;i <= n;i++){
// cout<<i<<' ';
// for(int j = 0;j < 2;j++) for(int k = 0;k < 2;k++) cout<<dp[i][j][k]<<' ';
// cout<<'\n';
// }
int ans = min(dp[1][0][0],dp[1][0][1]);
if(ans >= 1e9) cout<<"impossible";
else cout<<ans;
}
# | 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... |