You are a CEO of a group of companies (\(N\) companies form a rooted tree structure), and the country you live in has a weird tax system. Suppose if a company makes \(X\) rs profit then it has to pay \(Y\) rs tax, here the \(Y\) is the number of prime factors of \(X\).Calculate the total tax paid by all the companies in the group. Company 1 is the parent of all companies.
Tax paid by a company is equal to the tax paid by its direct children and the tax paid on the profits earned by that company.
Input :
The first line contains \(T\), the number of test cases (\(1 \leq T \leq 10^3\))
The first line of each test case contains \(N\), the number of companies (\(1 \leq N \leq 10^5\))
The second line of each test case contains an array profit \(a_1,a_2,a_3,....a_n\) (\(1 \leq a_i \leq 10^6\))
The next \((N-1)\) lines contain two numbers \(u,v\). There is an edge between \(u\) and \(v\)
The structure is guaranteed to be a tree.
It is guaranteed that the sum of \(N\) over all test cases doesn't exceed \(10^5\).
Output:
Print an array of size \(N\) ,where \(A_i\) is the amount of tax paid by the company \(i\)
2 3 10 12 16 1 3 1 2 3 4 4 4 1 2 2 3
5 2 1 3 2 1
In the first test case,Company 1 is the parent of company 2 and company 3. So the total prime factors of 10,12 and 16 are 2,2 and 1 respectively
So the tax paid by company 2 will be 2Rs and the tax paid by company 3 will be 1Rs.
Now company 1 will pay 2Rs as its own tax and 3Rs is already paid by its children companies
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor