Black White Tree

               Black White Tree

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.
image
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!

Add a Comment

Your email address will not be published. Required fields are marked *