Khaled is well known for his love of trees, and for the tree problems he can come up with. However, he is tired of all his problems being solved every time, so he decided to come up with a tree problem that no body can solve.
Khaled will give you a tree of $$$N$$$ vertices, such that each vertex $$$i$$$ is associated with value $$$A_i$$$, and vertex $$$1$$$ is the root vertex of the tree.
We call some chosen set of vertices of the given tree a Khaled-utiful Set of Beauty $$$K$$$ if it holds that for every chosen vertex $$$v$$$:
We define $$$F(K)$$$ as the maximum possible sum of values of some Khaled-utiful Set of Beauty $$$K$$$ of the given tree. You need to find $$$F(K)$$$ for all $$$K$$$ $$$(1 \le K \le N)$$$.
The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of testcases.
The first line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 2 \cdot 10^5)$$$ — the number of vertices in the tree.
The second line of each testcase contains $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^9)$$$ — the values associated with the nodes.
The following $$$N - 1$$$ lines contain the edges of the tree. Each line contains two integers $$$U$$$ and $$$V$$$ denoting an edge between vertices $$$U$$$ and $$$V$$$ $$$(1 \le U , V \le N , U \ne V)$$$. It is guaranteed that these edges form a tree.
It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$
For each testcase print a single line containing $$$N$$$ space-separated integers $$$S_1, S_2, \dots, S_N$$$, where the $$$S_i$$$ represents the value of $$$F(i)$$$.
2 4 1 2 3 4 1 2 1 3 2 4 2 100 1 1 2
7 9 10 10 100 101
