「BalticOI 2021 Day2」The Xana coup

题目描述

给定一棵包含 $N$ 个节点的树，第 $i$ 个节点有一个点权 $a_i$，其中 $a_i \in \{0,1\}$。

你可以执行切换操作：对节点 $i$ 执行切换操作会使得节点 $i$ 及其所有直接相邻的节点的点权取反（即 $0$ 变为 $1$，$1$ 变为 $0$）。

直接相邻指的是两个节点之间由一条边直接连接。

求至少需要多少次切换操作才能使得所有节点的点权都变为 $0$。如果无法实现，输出 impossible。

输入格式

第一行包含一个整数 $N$，表示树的节点数。

接下来 $N-1$ 行，每行包含两个整数，表示树的一条边。

最后一行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$，表示每个节点的初始点权。

输出格式

如果存在解，输出一个整数，表示最少需要的切换操作次数。

如果无解，输出 impossible。

样例

样例 1

输入

5
1 2
1 3
2 4
2 5
0 1 0 1 1

输出

4

其中 $a_i=0$ 为黑色，$a_i=1$ 为白色。 可以对点 $4,5,3,1$ 进行切换操作使得所有点的点权为 $0$。

样例 2

输入

5
1 2
2 3
3 4
4 5
0 1 1 1 1

输出

impossible

数据范围与提示

• 子任务 1（5 分）：$N \le 20$
• 子任务 2（15 分）：$N \le 40$
• 子任务 3（10 分）：如果节点 $u$ 和 $v$ 满足 $|u-v|=1$，那么它们之间有边相连（即树是一条链）
• 子任务 4（40 分）：每个节点最多与 $3$ 个节点相连
• 子任务 5（30 分）：无特殊限制

对于 $100\%$ 的数据，$3 \le N \le 10^5$。