CF429A.Xor-tree

Iahub 最近发明了一种名为 xor-tree（异或树）的新型树。他随后为孩子们设计了一个使用 xor-tree 的游戏。

游戏在一棵有 $n$ 个节点的树上进行，节点编号为 $1$ 到 $n$。每个节点 $i$ 有一个初始值 $\textit{init}_i$，为 $0$ 或 $1$。树的根节点为 $1$。

在游戏过程中，可以执行任意次（也可以是零次）操作。唯一可执行的操作是 选择一个节点 $x$：

• 节点 $x$ 的值翻转（$0 \to 1$，$1 \to 0$）
• $x$ 的子节点值不变
• $x$ 的孙子节点值翻转
• $x$ 的曾孙节点值不变
• ...以此类推，按深度交替

游戏的目标是让每个节点 $i$ 的值变为目标值 $\textit{goal}_i$（也是 $0$ 或 $1$）。你需要使用 最少 的操作次数达到目标。

第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

接下来 $n-1$ 行，每行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示节点 $u_i$ 和 $v_i$ 之间有一条边。

下一行包含 $n$ 个整数，第 $i$ 个数表示 $\textit{init}_i$（$0$ 或 $1$）。

再下一行包含 $n$ 个整数，第 $i$ 个数表示 $\textit{goal}_i$（$0$ 或 $1$）。

第一行输出一个整数 $\textit{cnt}$，表示最少的操作次数。

接下来的 $\textit{cnt}$ 行，每行输出一个整数 $x_i$，表示你选择的节点。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^5$。