Breaking Edges
Tag(s):

## Algorithms, Depth First Search, Easy, Graphs, Trees

Problem
Editorial
Analytics

You are given a tree (undirected connected graph with no cycles) consisting of N nodes and $N - 1$ edges. There is a number associated with each node $(v_i)$ of the tree. You can break any edge of the tree you want and this would result in formation of 2 trees which were part of the original tree.

Let us denote by $treeOr$, the bitwise OR of all the numbers written on each node in a tree.

You need to find how many edges you can choose, such that, if that edge was removed from the tree, the $treeOr$ of the 2 resulting trees is equal.

Input:

First line of input contains N, the number of nodes in the tree. Next line contains N space separated integers, $i^{th}$ of which denotes $v_i$. Each of the next $N - 1$ lines describe the edges of the tree. Each line contains 2 space separated integers A and B, meaning that there is an edge between nodes A and B.

Output:

Print the number of edges that can be chosen, such that, if that edge was removed from the tree, the $treeOr$ of the 2 resulting trees is equal.

Constraints:

$2 \le N \le 2 \times 10^5$

$0 \le v_i \le 1048575$

$1 \le A , B \le N$

$A \ne B$

SAMPLE INPUT
5
2 3 32 43 8
1 2
1 3
2 4
3 5
SAMPLE OUTPUT
1

Explanation

You can break the edge between nodes 2 and 4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Math > Geometry
• Algorithms > Dynamic Programming
• Math > Number Theory