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

?