#include <bits/stdc++.h>
using namespace std;
int const INF=1e9;
int const MAX=1e5+5;
int dp[MAX][2][2];
/// dp[nod][i][j]=nr minim de schimbari sa stingem tot subarborele
/// lui nod astfel incat nod sa aiba valoarea i si am aplicat
/// toggle sau nu pe acest nod
int aux[MAX][2][2];
int n;
vector<int>tree[MAX];
bool v[MAX];
void read(){
cin>>n;
int i;
for(i=1;i<n;++i){
int u,v;
cin>>u>>v;
tree[u].push_back(v);
tree[v].push_back(u);
}
for(i=1;i<=n;++i)
cin>>v[i];
}
void dfs(int nod,int tata){
int i;
for(i=0;i<2;++i){
aux[nod][i][0]=0;
aux[nod][i][1]=INF;
}
for(auto fiu : tree[nod])
if(fiu!=tata){
dfs(fiu,nod);
for(i=0;i<2;++i){
int aux0=min(aux[nod][i][0]+dp[fiu][i][0],aux[nod][i][1]+dp[fiu][i][1]);
int aux1=min(aux[nod][i][0]+dp[fiu][i][1],aux[nod][i][1]+dp[fiu][i][0]);
aux[nod][i][0]=min(INF,aux0);
aux[nod][i][1]=min(INF,aux1);
}
}
dp[nod][v[nod]][0]=aux[nod][0][0];
dp[nod][v[nod]][1]=aux[nod][1][1]+1;
dp[nod][!v[nod]][0]=aux[nod][0][1];
dp[nod][!v[nod]][1]=aux[nod][1][0]+1;
}
void write(int ans){
if(ans<INF)
cout<<ans;
else
cout<<"impossible";
}
int main()
{
read();
dfs(1,0);
write(min(dp[1][0][0],dp[1][0][1]));
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... |