Black White Tree

               Black White Tree

Click here to Solve the problem!!

Daisy has a tree with  node and  edges. Each node of the tree is colored either black or white. She defines the strangeness of a tree as the absolute difference between the number of black nodes and white nodes.

The tree in the example above has  black nodes and  white nodes, so the strangeness is .

One day Daisy got bored and decided to cut out a subtree with maximum strangeness. Can you help her to do that?

Note: A subtree of a tree is any of its connected subgraphs.

Input Format

• The first line contains , the number of nodes in the tree.
• The second line contains  space-separated integers . If , it means the  node is black. If , it means the  node is white.
• The  subsequent lines each contains two space-separated integers  and , which means that there is an edge between nodes  and .

Constraints

Subtasks

• For  of the maximum score, 
• For  of the maximum score, 
• For  of the maximum score, 

Output Format

In the first line, print the strangeness of the subtree. In the second line, print , the size of the subtree with maximum strangeness.

The third line should contain  space-separated integers denoting the nodes which are part of the subtree.

Sample Input 0

8
1 0 0 1 1 0 0 0
7 1
3 5
1 6
4 3
6 3
2 3
7 8

Sample Output 0

4
6
1 2 3 6 7 8

Explanation 0

The red subtree is the subtree with maximum strangeness. It has  white nodes and just one black node, the strangeness is .

Code:

coming soon...keep on checking this blog!

Please do comment If u have any Queries!