We Are Discuss About CODECHEF SOLUTION
Tree and Divisors Codechef Solution
Tree and Divisors Codechef Solution
Problem
You are given a tree with N vertices, rooted at vertex 1. The i-th vertex of this tree has the integer A_i written on it.
For each vertex u (1 \leq u \leq N), find the number of divisors of the product of all A_v such that v lies in the subtree of u.
Formally, for each u:
- Let S_u denote the set of vertices that lie in the subtree of u (including u).
- Define X_u = \prod_{v \in S_u} A_v
- Find the number of divisors of X_u
The answer may be large, so report it modulo 10^9 + 7.
Input Format
- The first line of input contains an integer T, denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains a single integer N, the number of vertices.
- The second line of each test case contains N space-separated integers A_1, A_2, \ldots, A_N — the values written on the vertices.
- The next N-1 lines describe the edges of the tree. The i-th of these N-1 lines contains two space-separated integers u_i and v_i, denoting an edge between vertices u_i and v_i.
Output Format
For each test case, output one line containing N space-separated integers. The i-th of these integers is the answer for vertex i.
Constraints
- 1 \leq N \leq 3\cdot 10^4
- 1 \leq A_i \leq 10^6
- 1 \leq u_i, v_i \leq N
- The edges given in the input describe a tree.
- The sum of N across all test cases won’t exceed 3 \cdot 10^4.
Sample 1:
Input
Output
3 4 100 101 102 103 1 2 1 3 1 4 4 2 2 2 2 1 2 2 3 3 4 5 43 525 524 12 289 1 2 1 3 3 4 4 5
192 2 8 2 5 4 3 2 1080 12 60 18 3
Explanation:
Test case 1: The answers are as follows:
- For u = 2, X_u = 101 which is prime and so has two factors.
- For u = 4, X_u = 103 which is prime and so has two factors.
- For u = 3, X_u = 102 which has 8 factors, namely \{1, 2, 3, 6, 17, 34, 51, 102\}.
- For u = 1, X_u = 106110600, which has 192 factors.
More Info
SOLUTION
Tree and Divisors Codechef Solution
Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW