Bitwise Tree

4.5

4 votes
Dynamic Programming, Algorithms, Graphs, Depth First Search
Problem

You are given a tree consisting of N nodes, where the ith node has a value Ai assigned to it.

You can do the following operation any number of times. In an operation, you can :

  • Select a node i(1iN) and set Ai=Ai2.

Find the minimum number of operations to be performed so that the bitwise AND of the values present in any two adjacent nodes of the tree is zero.

  Input format

  • The first line of input contains an integer N denoting the number of nodes in the tree.
  • The second line contains N integers A1,A2,,AN, denoting the values assigned to the nodes.
  • N1 lines follow. The ith line contains two integers Xi,Yi denoting a edge between the nodes Xi,Yi.It is guaranteed that the nodes and edges form a tree.

Output format
For each query, print the minimum number of operations to be performed so that the bitwise AND of the values present in any two adjacent nodes of the tree is zero.

Constraints

2N1051Ai1031Xi<YiN

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

One possible sequence of operations is: Apply the operation on the node 1 twice making A1=0, node 3 once making A3=2, node 6 once making A6=1. 

Editor Image

?