Codigos/429A.cpp at master · tfarnecim/Codigos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

//biblioteca
#define INF  1000000000
#define INFL 1000000000000000000
#define mp make_pair
#define alfa "abcdefghijklmnopqrstuvwxyz"
#define FASTIO ios::sync_with_stdio(false)
#define TIE cin.tie(NULL)
#define P system("pause")
#define PI 3.14159265358

typedef long long ll;
typedef vector <ll> vi;
typedef pair <ll,ll> pii;

ll MAX(ll a,ll b){
	if(a>b)return a;
	return b;
}

ll MIN(ll a,ll b){
	if(a<b)return a;
	return b;
}

vi grafo[200000];
bool passou_solve[200000];
bool passou[200000];
int dis[200000];
int res;
bool ini[200000];
bool fim[200000];
vi out;

void dfs(int v){

	passou[v] = true;

	for(int i=0;i<grafo[v].size();i++){

		int adj = grafo[v][i];

		if(!passou[adj]){
			dis[adj] = dis[v]+1;
			dfs(adj);
		}

	}

}

void dfs_solve(int v,int mi,int mp){

	passou_solve[v] = true;

	bool aux = ini[v];

	if(dis[v]%2==0){

	    if((ini[v]==fim[v] && mp%2!=0) || (ini[v]!=fim[v] && mp%2==0)){
			mp++;
			out.push_back(v);
		}

	}else{

		if((ini[v]==fim[v] && mi%2!=0) || (ini[v]!=fim[v] && mi%2==0)){
			mi++;
			out.push_back(v);
		}

	}

	for(int i=0;i<grafo[v].size();i++){

		int adj = grafo[v][i];

		if(!passou_solve[adj]){
			dfs_solve(adj,mi,mp);
		}

	}

}

int main(){

	FASTIO;

	int n;

	cin >> n;

	for(int i=0;i<n-1;i++){

		int a,b;

		cin >> a >> b;

		grafo[a].push_back(b);
		grafo[b].push_back(a);

	}

	dfs(1);

	for(int i=1;i<=n;i++) cin >> ini[i];
	for(int i=1;i<=n;i++) cin >> fim[i];

	dfs_solve(1,0,0);

	cout << out.size() << endl;

	for(int i=0;i<out.size();i++){
		cout << out[i] << "\n";
	}

	return 0;
}