Yesterday I encountered this problem in a hiring contest.

Problem:

You are given the following:

1. A tree T consisting of n nodes

2. An integer x

3. Each node has some value w[i] associated with it.

Task

Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x.

Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once.

Example

Assumptions

n = 3 w = [3,2,2] edges = [(1,2), (1,3)] x = 1 Approach

There exist two simple paths such that bitwise xor of elements on the path is x Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator. Therefore, print 2.

Any approach?