# Divisor Power in a Rooted Tree
## Problem Statement
You are given a rooted tree consisting of $n$ nodes, rooted at node 1. Each node $k$ is associated with an integer value, denoted as $a_k$.
Let's define two helper functions:
* $D(X)$: The number of divisors of an integer $X$. For example, $D(12) = 6$ because 12 has divisors $\{1, 2, 3, 4, 6, 12\}$.
* $COUNT(i, \text{val})$: The frequency of the integer value $\text{val}$ among all node values in the subtree of node $i$.
The **Divisor Power** of each node $i$ is defined as:
$$\text{DivisorPower}(i) = \sum_{j \in \text{subtree}(i)} D(a_j) \cdot COUNT(i, a_j)$$
Your task is to compute the Divisor Power for each node in the tree.
## Input Format
- First line: an integer $n$ ($2 \le n \le 10^5$) — the number of nodes in the tree.
- Second line: $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_k \le 10^6$) — the values associated with nodes $1, 2, \dots, n$ respectively.
- The next $n - 1$ lines: each contains two space-separated integers $u$ and $v$ ($1 \le u, v \le n$), denoting an edge between nodes $u$ and $v$.
## Output Format
Print $n$ space-separated integers — the Divisor Power of each node from $1$ to $n$.
## Sample Test Cases
### Sample Input 1
```
3
6 2 6
1 2
1 3
```
### Sample Output 1
```
18 2 4
```
### Sample Input 2
```
5
10 1 5 10 2
1 2
1 3
2 4
2 5
```
### Sample Output 2
```
21 7 2 4 2
```
## Constraints
- $2 \le n \le 10^5$
- $1 \le a_k \le 10^6$
- $1 \le u, v \le n$
- The given edges form a tree.
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1:
Nodes: 1, 2, 3. Values: $a_1=6, a_2=2, a_3=6$. Edges: (1,2), (1,3). Root is 1.
* Divisors:
* $D(6) = 4$ (divisors: $\{1,2,3,6\}$)
* $D(2) = 2$ (divisors: $\{1,2\}$)
* **Node 1:** Subtree of 1 includes nodes $\{1,2,3\}$ with values $\{6,2,6\}$.
* $COUNT(1, 6) = 2$ (nodes 1 and 3 have value 6)
* $COUNT(1, 2) = 1$ (node 2 has value 2)
* $\text{DivisorPower}(1) = D(a_1) \cdot COUNT(1, a_1) + D(a_2) \cdot COUNT(1, a_2) + D(a_3) \cdot COUNT(1, a_3)$
* $= D(6) \cdot COUNT(1, 6) + D(2) \cdot COUNT(1, 2) + D(6) \cdot COUNT(1, 6)$
* $= 4 \cdot 2 + 2 \cdot 1 + 4 \cdot 2 = 8 + 2 + 8 = 18$
* **Node 2:** Subtree of 2 includes node $\{2\}$ with value $\{2\}$.
* $COUNT(2, 2) = 1$
* $\text{DivisorPower}(2) = D(a_2) \cdot COUNT(2, a_2) = D(2) \cdot 1 = 2 \cdot 1 = 2$
* **Node 3:** Subtree of 3 includes node $\{3\}$ with value $\{6\}$.
* $COUNT(3, 6) = 1$
* $\text{DivisorPower}(3) = D(a_3) \cdot COUNT(3, a_3) = D(6) \cdot 1 = 4 \cdot 1 = 4$
Output: `18 2 4`
### Sample 2:
Nodes: 1, 2, 3, 4, 5. Values: $a_1=10, a_2=1, a_3=5, a_4=10, a_5=2$. Edges: (1,2), (1,3), (2,4), (2,5). Root is 1.
* Divisors:
* $D(10) = 4$
* $D(1) = 1$
* $D(5) = 2$
* $D(2) = 2$
* **Node 1:** Subtree $\{1,2,3,4,5\}$, values $\{10,1,5,10,2\}$.
* $COUNT(1, 10) = 2$, $COUNT(1, 1) = 1$, $COUNT(1, 5) = 1$, $COUNT(1, 2) = 1$.
* $\text{DivisorPower}(1) = D(10) \cdot 2 + D(1) \cdot 1 + D(5) \cdot 1 + D(10) \cdot 2 + D(2) \cdot 1 = 4 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 + 4 \cdot 2 + 2 \cdot 1 = 8+1+2+8+2 = 21$.
* **Node 2:** Subtree $\{2,4,5\}$, values $\{1,10,2\}$.
* $COUNT(2, 1) = 1$, $COUNT(2, 10) = 1$, $COUNT(2, 2) = 1$.
* $\text{DivisorPower}(2) = D(1) \cdot 1 + D(10) \cdot 1 + D(2) \cdot 1 = 1 \cdot 1 + 4 \cdot 1 + 2 \cdot 1 = 1+4+2 = 7$.
* **Node 3:** Subtree $\{3\}$, value $\{5\}$.
* $COUNT(3, 5) = 1$.
* $\text{DivisorPower}(3) = D(5) \cdot 1 = 2 \cdot 1 = 2$.
* **Node 4:** Subtree $\{4\}$, value $\{10\}$.
* $COUNT(4, 10) = 1$.
* $\text{DivisorPower}(4) = D(10) \cdot 1 = 4 \cdot 1 = 4$.
* **Node 5:** Subtree $\{5\}$, value $\{2\}$.
* $COUNT(5, 2) = 1$.
* $\text{DivisorPower}(5) = D(2) \cdot 1 = 2 \cdot 1 = 2$.
Output: `21 7 2 4 2`
Loading problem statement...