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_iAi​ written on it.

For each vertex $u$ ($1\le u\le N$), find the number of divisors of the product of all A_vAv​ such that $v$ lies in the subtree of $u$.

Formally, for each $u$:

• Let S_uSu​ denote the set of vertices that lie in the subtree of $u$ (including $u$).
• Define X_u = \prod_{v \in S_u} A_vXu​=∏v∈Su​​Av​
• Find the number of divisors of X_uXu​

The answer may be large, so report it modulo 10^9 + 7109+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_NA1​,A2​,…,AN​ — 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_iui​ and v_ivi​, denoting an edge between vertices u_iui​ and v_ivi​.

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

Sample 1:

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