You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

你可以进行切换操作：

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

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

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

输入格式

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

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

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

输出格式

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

如果无解，输出 impossible。

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

4

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

impossible

提示

样例 1 解释

$a_i=0$ 为黑色，$a_i=1$ 为白色。

可以对点 $4,5,3,1$ 进行切换操作使得所有点的点权为 $0$。

数据规模与约定

本题采用捆绑测试。

• 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$。

说明

翻译自 BalticOI 2021 Day2 C The Xana coup。