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 initi, 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 xflips, 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 goali, 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⁵). 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 initi (initi is either 0 or 1). The following line also contains ninteger numbers, the i-th number corresponds to goali (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. cells into walls so that all the remaining cells still formed a connected area. Help him.

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

题意：

 给出一棵树，有n个节点，根为1，每个节点的值不是0就是1，每次可以翻转一个节点，翻转后，当前节点值翻转，儿子节点值不变，儿子的儿子翻转，依次类推，求最少翻转次数，使得每个节点的值与目标结果相同。

题解:

 由于翻转一个节点，其子节点有的会改变，因此贪心的从根开始搜索，如果当前节点与目标不同，那么一定要翻转，因为只影响子节点，因此其父节点已经到达目标结果将不受影响。

#include<bits/stdc++.h>using namespace std;const int maxn = 100005;int init[maxn],goal[maxn];vector<int>ans,itv[maxn];void dfs(int u,int fa,int odd,int even){	if (odd)	init[u] ^= 1;	if (init[u] != goal[u])	{		odd ^= 1;		ans.push_back(u);	}	int size = itv[u].size();	for (int i = 0;i < size;i++)	{		int v = itv[u][i];		if (fa == v)	continue;  //树是双向的，因此此处保证从根单向搜索		dfs(v,u,even,odd);	}}int main(){	int n,u,v;	scanf("%d",&n);	for (int i = 1;i < n;i++)	{		scanf("%d%d",&u,&v);		itv[u].push_back(v);		itv[v].push_back(u);	}	for (int i = 1;i <= n;i++)	scanf("%d",&init[i]);	for (int i = 1;i <= n;i++)	scanf("%d",&goal[i]);	dfs(1,1,0,0);	int size = ans.size();	printf("%d\n",size);	for (int i = 0;i < size;i++)	printf("%d\n",ans[i]);	return 0;}