| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1105528 | andrewp | The Xana coup (BOI21_xanadu) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
using pii=pair<int,int>;
using pll=pair<int,int>;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ldb double
#define all(x) x.begin(),x.end()
#define raint(x) x.rbegin(),x.rend()
void rd(int&x){scanf("%d",&x);}
void rd(ll&x){scanf("%lld",&x);}
void rd(char*x){scanf("%s",x);}
void rd(ldb&x){scanf("%lf",&x);}
void rd(string&x){scanf("%s",&x);}
int ri(){int x;rd(x);return x;}
#ifndef ONLINE_JUDGE
#include "C:\Users\andre\Downloads\cpp-dump-0.7.0\cpp-dump-0.7.0\cpp-dump.hpp"
#define dbg(...) cpp_dump(__VA_ARGS__)
#else
#define dump(...)
#endif
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&i:x)rd(i);}
template<typename T,typename...A>void rd(T&x,A&...args){rd(x);rd(args...);}
template<typename T>void rd(){T x;rd(x);return x;}
template<typename T>vector<T> rv(int n){vector<T> x(n);rd(x);return x;}
const int N=1e5+50;
int n,a[N],dp[N][2][2];
vector<int> G[N];
void dfs(int x,int par){
if(!a[x]){
dp[x][0][1]=dp[x][1][0]=N;
dp[x][0][0]=0;
dp[x][1][1]=1;
}else{
dp[x][0][0]=dp[x][1][1]=N;
dp[x][0][1]=1;
dp[x][1][0]=0;
}
for(int u:G[x]){
if(u!=par){
dfs(u,x);
for(int k=0;k<2;k++){
int f=dp[x][0][k],s=dp[x][1][k];
dp[x][0][k]=min(dp[u][k][0]+f,dp[u][k][1]+s);
dp[x][1][k]=min(dp[u][k][1]+f,dp[u][k][0]+s);
}
}
}
}
int main(){
n=ri();
for(int i=1;i<n;i++){
int u,v; rd(u,v);
G[u].pb(v);
G[v].pb(u);
}
for(int i=1;i<=n;i++) a[i]=ri();
dfs(1,1);
int ans=min(dp[1][0][0],dp[1][0][1]);
if(ans>n) printf("impossible\n");
else printf("%d\n",ans);
return 0;
}