← 返回题目列表

Codeforces · 429/A

A. 异或树

中文机器翻译题面 查看原题

Iahub 对他最近的发现——繁殖树木感到非常自豪。现在,他发明了一种新树,称为异或树。在这一革命性的新发现之后,他发明了一种使用异或树的儿童游戏。

游戏在具有 n 个节点的树上进行,节点编号为 1 到 n。每个节点 i 都有一个初始值 initi,该值不是 0 就是 1。树的根是节点 1。

在游戏过程中,人们可以对树执行多次(可能为零)操作。唯一可用的操作类型是选择节点 x。在有人选择节点 x 后,节点 x 的值翻转,x 的儿子的值保持不变,x 的儿子的儿子的值翻转,x 的儿子的儿子的儿子的值保持不变,依此类推。

游戏的目标是让每个节点 i 都有值 goali,也可以仅为 0 或 1。您需要使用最少的操作次数来达到游戏的目标。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n; ui ≠ vi),这意味着节点 ui 和 vi 之间有一条边。

下一行包含n个整数,其中第i个对应于initi(initi为0或1)。下面一行也包含 n 个整数,第 i 个数字对应于 goali(goali 为 0 或 1)。

输出

在第一行输出一个整数cnt,代表您执行的最少操作数。接下来的 cnt 行中的每一行都应包含一个整数 xi,表示您选择一个节点 xi。

示例

输入 #1

10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1

输出 #1

2
4
7