A9566 · Xor-tree · GESP考级

题目描述

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$，表示你选择的节点。

输入 #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