This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+10;
const int inf=0x3f3f3f3f3f3f;
int n,a[MAXN],tot,head[MAXN];
int dp[MAXN][2][2],f[MAXN][2][2],rt=1,siz[MAXN];
struct node{
int nxt,to;
}e[MAXN*4];
void add(int x,int y){
e[++tot].nxt=head[x];
e[tot].to=y;
head[x]=tot;
}
void dfs(int x,int fa){
//dp i 0/1 0/1 表示第i个节点 对父节点影响 相等/取反
dp[x][0][0]=0;
dp[x][1][1]=1;
dp[x][1][0]=inf;
dp[x][0][1]=inf;
int as,bs,cs,ds;
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].to;
if(to==fa)continue;
dfs(to,x);
as=min(dp[x][0][0]+dp[to][0][a[to]],dp[x][0][1]+dp[to][1][a[to]]);
bs=min(dp[x][0][1]+dp[to][0][a[to]],dp[x][0][0]+dp[to][1][a[to]]);
cs=min(dp[x][1][0]+dp[to][0][!a[to]],dp[x][1][1]+dp[to][1][!a[to]]);
ds=min(dp[x][1][1]+dp[to][0][!a[to]],dp[x][1][0]+dp[to][1][!a[to]]);
dp[x][0][0]=as;dp[x][0][1]=bs;dp[x][1][0]=cs;dp[x][1][1]=ds;
}
}
signed main(){
cin>>n;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0);
if(min(dp[1][0][a[1]],dp[1][1][a[1]])>=inf){
cout<<"impossible";
}else cout<<min(dp[1][0][a[1]],dp[1][1][a[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... |