[AdditionalFile3563.zip](file://AdditionalFile3563.zip?type=additional_file)

#3563. 「BalticOI 2021 Day2」The Xana coup

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2021 Day2「The Xana coup」，译者 Shuchong。

给定一棵点数为 $N$ 个树，第 $i$ 个点有点权 $a_i$，$a_i \in \{0,1\}$。

你可以进行切换操作：

• 对点 $i$ 进行切换操作会使得点 $i$ 及与其 直接相连 的点的点权取反。

其中直接相连指两点之间恰好只有一条边。

求至少需要多少次切换操作才能使得所有点的点权变为 $0$。

输入格式

第一行一个整数 $N$ 代表树的点数。

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

第 $N+1$ 行 $N$ 个整数 $a_i$ 代表第 $i$ 个点的点权。

输出格式

如果有解，一行一个整数代表答案。

如果无解，输出 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

数据范围与提示

• Subtask 1（5 pts）：$N \le 20$。
• Subtask 2（15 pts）：$N \le 40$。
• Subtask 3（10 pts）：如果点 $u$ 和点 $v$ 满足 $|u-v|=1$，那么他们有边相连。
• Subtask 4（40 pts）：一个点最多与 $3$ 个点相连。
• Subtask 5（30 pts）：无特殊限制。

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