考虑以 \(1\) 为根进行树形 dp，定义 \(f_{x,0/1,0/1}\) 表示以 \(x\) 为根子树内除了 \(x\) 外都已变为 \(0\)，\(x\) 的点权为 \(0/1\)（对应第一个 \(0/1\)），\(x\) 父亲的点权会不会反转（对应第二个 \(0/1\)）。不合法状态设为 \(+\infty\)。
首先，对于叶子节点，显然有 \(f_{x,a_x,0}=0,f_{x,a_x\oplus1,1}=1\)。
考虑转移，设 \(g_{i,0}\) 表示考虑 \(x\) 的前 \(i\) 个儿子全是点权为 \(0\)，对 \(x\) 的反转次数和为偶数，\(g_{i,1}\) 表示考虑 \(x\) 的前 \(i\) 个儿子全是点权为 \(0\)，对 \(x\) 的反转次数和为奇数。显然 \(g_{0,0}=0,g_{0,1}=+\infty\)。
再设 \(h_{i,0}\) 表示考虑 \(x\) 的前 \(i\) 个儿子全是点权为 \(1\)，对 \(x\) 的反转次数和为偶数，\(h_{i,1}\) 表示考虑 \(x\) 的前 \(i\) 个儿子全是点权为 \(1\)，对 \(x\) 的反转次数和为奇数。显然 \(h_{0,0}=0，h_{0,1}=+\infty\)。
显然，对于 \(x\) 的儿子 \(y\)，上述这四个状态的转移有：
-
\(g_{i,0}=\min(g_{i-1,0}+f_{y,0,0},g_{i-1,1}+f_{y,0,1})\)
-
\(g_{i,1}=\min(g_{i-1,0}+f_{y,0,1},g_{i-1,1}+f_{y,0,0})\)
-
\(h_{i,0}=\min(h_{i-1,0}+f_{y,1,0},h_{i-1,1}+f_{y,1,1})\)
-
\(h_{i,1}=\min(h_{i-1,0}+f_{y,1,1},h_{i-1,1}+f_{y,1,0})\)
设 \(x\) 的儿子数量为 \(son_x\)，则有
-
不在当前点进行操作，\(x\) 没被反转，即 \(f_{x,a_x,0}=g_{son_x,0}\)
-
不在当前点进行操作，\(x\) 被反转，即 \(f_{x,a_x\oplus1,0}=g_{son_x,1}\)
-
在当前点进行操作，\(x\) 没被反转，即 \(f_{x,a_x,1}=h_{son_x,1}+1\)
-
在当前点进行操作，\(x\) 被反转，即 \(f_{x,a_x\oplus1,1}=h_{son_x,0}+1\)
直接转移即可，最后答案为 \(\min(f_{1,0,0},f_{1,0,1})\)。
#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
const int inf=1e12;
int n,a[MAXN],f[MAXN][2][2];
int head[MAXN],cnt;
struct Edge{int value,next;
}edge[MAXN*2];
void addedge(int u,int v){edge[++cnt].value=v;edge[cnt].next=head[u];head[u]=cnt;
}
void dfs(int x,int fa){bool flag=0;int ga=0,gb=inf,ha=0,hb=inf;for(int i=head[x];i;i=edge[i].next){int y=edge[i].value;if(y!=fa){dfs(y,x);flag=1;int tga=min(ga+f[y][0][0],gb+f[y][0][1]);int tgb=min(ga+f[y][0][1],gb+f[y][0][0]);int tha=min(ha+f[y][1][0],hb+f[y][1][1]);int thb=min(ha+f[y][1][1],hb+f[y][1][0]);ga=tga,gb=tgb,ha=tha,hb=thb;}}if(!flag){f[x][a[x]][0]=0;f[x][a[x]^1][1]=1;}else{f[x][a[x]][0]=ga;f[x][a[x]^1][0]=gb;f[x][a[x]][1]=hb+1;f[x][a[x]^1][1]=ha+1;}
}
signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);scanf("%lld",&n);for(int i=1;i<n;i++){int u,v;scanf("%lld%lld",&u,&v);addedge(u,v),addedge(v,u);}for(int i=1;i<=n;i++)scanf("%lld",&a[i]),f[i][0][0]=f[i][0][1]=f[i][1][0]=f[i][1][1]=inf;dfs(1,0);int ans=min(f[1][0][0],f[1][0][1]);if(ans<inf)printf("%lld\n",ans);else printf("impossible\n");return 0;
}