All Tracks Algorithms Graphs Depth First Search Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?