CFR 245 1A. Xor-tree ( Greedy + DFS )

Problem - 429A - Codeforces
It is obvious that if all nodes above are cleared and the current node is not the target, it has to be flipped. It is never better to flip its ancestors, for it will cost extra for nothing. We don't have to go down everytime to flip all grandson nodes, but just record two types of flag, one for odd level sons, and one for even level sons.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;

int n;
vector< int > G[ MAXN ];
int ini[ MAXN ], gol[ MAXN ];

vector< int > ans;

void dfs( int u, int fa, int dpt, vector< int > flag ){
    if( ini[ u ] ^ flag[ dpt & 1 ] != gol[ u ] )
        flag[ dpt & 1 ] ^= 1,
        ans.push_back( u );
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        dfs( v, u, dpt + 1, flag );
    }
}

void solve(){
    dfs( 1, -1, 0, vector< int >{ 0, 0 } );
    printf("%d\n", (int)ans.size());
    for( int u : ans )
        printf("%d\n", u);
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n - 1; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        G[ u ].push_back( v );
        G[ v ].push_back( u );
    }
    for( int u = 1; u <= n; ++u )
        scanf("%d", ini + u);
    for( int u = 1; u <= n; ++u )
        scanf("%d", gol + u);
    solve();
    return 0;
}