Aomine's Last Game

Aomine Daiki, the miraculous Basket Ball player from The Generation of Miracles is not yet defeated in any of his games until he met the duo, Kuroko and Kagami. 

Finally, during his game, he achieved an unknown state called The Zone.

He can now analyse the basketball court as a set of $N$ nodes connected with $N-1$ edges. These set of $N$ nodes are rooted at node 1. For each of the $N$ node, he assumes one of the two conditions:

• 1, if the node is to be visited in his drive to perform a freestyle basket.
• 0, if the node is not be visited in his drive to perform a freestyle basket.

However, in the drift of his exhilarating match, he finds that some nodes don't satisfy his expected assumption.

He can, thus, perform an operation on any of the given node such that:

• he can invert the condition of the node and if he inverts the condtion of a particular node, the sons of this node don't get their conditions inverted but the sons of sons of the node get their conditions inverted but the sons of sons of sons don't and so on..

Inverting the condition means that if the condition of node is 1, then it is made 0, else its made 1.

Find the minimum number of operations that he must perform and the nodes at which he must perform so that all the nodes satisfy his assumption and he can destroy the enemy team's morale.

 

Example:

Input: 5
1 2
2 3
1 4
4 5
1 0 0 1 1
0 1 0 1 1
Output: 4
1
2
3
5

Approach

Java

import java.util.ArrayList;
import java.util.Collections;

public class AomineLastGame {
    static long mod = 1000000007;
    static long maxX = (long) 1e18;
    static long mod2 = 998244353;

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int[] real, expected;
    static int[] flag;
    static ArrayList<Integer> ans;

    public static void main(String[] args) {

        int n = 5;
        graph = new ArrayList[n];
        visited = new boolean[n];
        real = new int[n];
        expected = new int[n];
        flag = new int[n];

        int arr[][] = { { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } };

        int arrN[][] = { { 1, 0, 0, 1, 1 }, { 0, 1, 0, 1, 1 } };

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 1; i < n; i++) {
            int a = arr[i - 1][0] - 1;
            int b = arr[i - 1][1] - 1;

            graph[a].add(b);
            graph[b].add(a);
        }

        for (int i = 0; i < n; i++)
            real[i] = arrN[0][i];
        for (int i = 0; i < n; i++)
            expected[i] = arrN[1][i];

        ans = new ArrayList<>();

        change(0, 0, 0, 0);

        System.out.println(ans.size());

        Collections.sort(ans);

        for (int i : ans) {
            System.out.println(i);
        }
    }

    static void change(int curr, int d, int odd, int even) {

        visited[curr] = true;

        if (d % 2 == 0) {
            if ((real[curr] + even) % 2 != expected[curr]) {
                even ^= 1;
                ans.add(curr + 1);
            }

        } else {
            if ((real[curr] + odd) % 2 != expected[curr]) {
                odd ^= 1;
                ans.add(curr + 1);
            }
        }

        for (int i : graph[curr]) {
            if (!visited[i]) {
                change(i, d + 1, odd, even);
            }
        }

    }

}