Xor-tree

题意翻译

lahub发明了一种异或树，并发明了一个使用异或树的游戏。 游戏在一棵有$N$个节点、根节点为$1$的树上进行，每个节点的初始值为$0$或$1$。 定义游戏中的一次操作: - 选择一个节点$x$ - $x$的值翻转，$x$的儿子的值不翻转，$x$的孙子的值翻转，$x$的孙子的儿子不翻转，以此类推。 游戏存在一个目标值，问最少多少次操作能使树中每个节点的值都等于目标值。 输出最少操作次数和操作方案。

题目描述

Iahub is very proud of his recent discovery, propagating trees. Right now, he invented a new tree, called xor-tree. After this new revolutionary discovery, he invented a game for kids which uses xor-trees. The game is played on a tree having $ n $ nodes, numbered from $ 1 $ to $ n $ . Each node $ i $ has an initial value $ init_{i} $ , which is either 0 or 1. The root of the tree is node 1. One can perform several (possibly, zero) operations on the tree during the game. The only available type of operation is to pick a node $ x $ . Right after someone has picked node $ x $ , the value of node $ x $ flips, the values of sons of $ x $ remain the same, the values of sons of sons of $ x $ flips, the values of sons of sons of sons of $ x $ remain the same and so on. The goal of the game is to get each node $ i $ to have value $ goal_{i} $ , which can also be only 0 or 1. You need to reach the goal of the game by using minimum number of operations.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ). Each of the next $ n-1 $ lines contains two integers $ u_{i} $ and $ v_{i} $ ( $ 1<=u_{i},v_{i}<=n $ ; $ u_{i}≠v_{i} $ ) meaning there is an edge between nodes $ u_{i} $ and $ v_{i} $ . The next line contains $ n $ integer numbers, the $ i $ -th of them corresponds to $ init_{i} $ ( $ init_{i} $ is either 0 or 1). The following line also contains $ n $ integer numbers, the $ i $ -th number corresponds to $ goal_{i} $ ( $ goal_{i} $ is either 0 or 1).

输出格式

In the first line output an integer number $ cnt $ , representing the minimal number of operations you perform. Each of the next $ cnt $ lines should contain an integer $ x_{i} $ , representing that you pick a node $ 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