CF429A Xor-tree

Iahub 对他最近的发现——传播树感到非常自豪。现在，他发明了一种新的树，称为 xor-树。在这个革命性的发现之后，他为孩子们设计了一种利用 xor-树的游戏。 游戏在一棵有 $n$ 个节点的树上进行，节点编号为 $1$ 到 $n$。每个节点 $i$ 有一个初始值 $init_{i}$，取值为 0 或 1。树的根节点是第 1 个节点。 在游戏过程中，可以对树进行若干次（也可以为零次）操作。唯一允许的操作是选择一个节点 $x$。当有人选择节点 $x$ 后，节点 $x$ 的值会翻转，$x$ 的儿子的值保持不变，$x$ 的孙子的值又会翻转，$x$ 的曾孙的值仍保持不变，依此类推，也就是“隔代翻转”。 游戏的目标是使每个节点 $i$ 达到目标值 $goal_{i}$，也只能是 0 或 1。你需要用最少次数的操作达到游戏目标。

第一行包含一个整数 $n$，表示节点的数量（$1 \leq n \leq 10^{5}$）。接下来的 $n-1$ 行，每行包含两个整数 $u_{i}$ 和 $v_{i}$（$1 \leq u_{i}, v_{i} \leq n$，$u_{i} \neq v_{i}$），表示 $u_{i}$ 和 $v_{i}$ 之间有一条边。 下一行包含 $n$ 个整数，第 $i$ 个整数为 $init_{i}$（$init_{i}$ 只能为 0 或 1）。再下一行包含 $n$ 个整数，第 $i$ 个整数为 $goal_{i}$（$goal_{i}$ 只能为 0 或 1）。

第一行输出一个整数 $cnt$，表示你所执行的最少操作次数。接下来的 $cnt$ 行，每行一个整数 $x_{i}$，表示你选择了节点 $x_{i}$ 进行操作。

由 ChatGPT 5 翻译