# Tree and Divisors Codechef Solution

### We Are Discuss About 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 = 2X_u = 101 which is prime and so has two factors.
• For u = 4X_u = 103 which is prime and so has two factors.
• For u = 3X_u = 102 which has 8 factors, namely \{1, 2, 3, 6, 17, 34, 51, 102\}.
• For u = 1X_u = 106110600, which has 192 factors.

## Tree and Divisors Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW