All Tracks Algorithms Dynamic Programming Problem

Tree of Numbers
Tag(s):

Algorithms, Dynamic Programming, Medium-Hard

Problem
Editorial
Analytics

You are given a tree of $$n$$ nodes, some of the nodes contain numbers and others don't. Your task is to compute the number of ways to complete the labeling of the tree rooted at $$1$$, such that the following condition is satisfied "for any subtree $$x$$ all elements of the subtree must divide its root".

Input:

First line contains a single integer $$n$$, denoting the number of nodes in the tree.
Next Line contains $$n$$ integers, each number describes the content of a node in order (e.g: first number describes content of node 1, second describes content of node 2, ... etc). If a number is $$0$$, it means that the content is unknown.
Next $$n-1$$ lines contain each two numbers $$(u, v)$$, meaning that there is an edge between node $$u$$ and node $$v $$.

Output:

Ouput a single integer denoting the number of ways to fill the tree without breaking the constraint modulo $$10^9+7$$;

Constraints:

  • $$1 \le n \le 10^5$$.
  • All numbers are non negative and less than or equal 10^9.
  • The root's content is always known.
SAMPLE INPUT
3
2 0 0
1 2
2 3
SAMPLE OUTPUT
3
Explanation

The possible labelling are:

  1. 2 2 2
  2. 2 2 1
  3. 2 1 1
Time Limit: 2.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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications