Black and White Tree solution codechef – You are given an undirected tree having N nodes. The color of each node is either Black or White. In one step, you can choose a node u, toggle the color of the chosen node u, as well as toggle the colors of all the nodes v, such that {u,v} is an edge in the tree. Can you find out the minimum number of steps required to make the color of all

You are given an undirected tree having NN nodes. The color of each node is either Black or White.

In one step, you can choose a node uu, toggle the color of the chosen node uu, as well as toggle the colors of all the nodes vv, such that {u,v}{u,v} is an edge in the tree.

Can you find out the minimum number of steps required to make the color of all the nodes black?

Note: Since the input is large, prefer using fast input methods.

Input Format Black and White Tree solution codechef

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of the TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line of each test case contains NN space separated integers A1,A2,...,ANA1,A2,…,ANAiAi = 0 represents that the initial color of the ithith node is black. AiAi = 1 represents that the initial color of the ithith node is white.
  • The following N1N−1 lines contain two space-separated integers xx and yy, which denotes that there is an edge between nodes xx and yy.

Output Format Black and White Tree solution codechef

For each test case, output in a single line the minimum number of steps required to make the color of all the nodes black.

Output 1−1 if it is impossible to make the color of all the nodes black.

Constraints Black and White Tree solution codechef

  • 1T51041≤T≤5⋅104
  • 1N1051≤N≤105
  • 0Ai10≤Ai≤1
  • 1x,yN1≤x,y≤N
  • The sum of NN over all test cases does not exceed 51055⋅105

Sample Input 1  Black and White Tree solution codechef 

3 
3
0 0 0
1 2
1 3
3
1 1 1
1 2
1 3
3
0 1 0
1 2
1 3

Sample Output 1  Black and White Tree solution codechef 

0
1
2

Explanation

Test Case 11: All the nodes are already black, so we do not need to do anything.

Test Case 22: All the nodes are white. If we choose node 11 in the first step, all the nodes will become black. Hence, only 11 step is required to make all the nodes black.

Test Case 33: Choose node 33 in the first step. This will make all the nodes white. Choose node 11 in the second step. This will make all the nodes black.

Leave a Comment