Problem Description
Stormtroopers were the assault/policing troops of the Galactic Empire. Dissenting citizens referred to them as bucketheads, a derogatory nickname inspired by the bucket-shaped helmets of stormtroopers. They wore white armor made from plastoid over a black body glove which, in addition to creating an imposing image, was outfitted with a wide array of survival equipment and temperature controls that allowed its wearer to survive in most environments, and were designed to disperse blaster bolt energy. As members of the Stormtrooper Corps, an independent branch that operated under the Imperial Army, stormtroopers represented the backbone of the Imperial Military—trained for total obedience to the command hierarchy, as well as absolute loyalty to Emperor Sheev Palpatine and the Imperial regime. Stormtroopers were trained at Imperial Academies, and used a variety of weapons.
--- Wookieepedia
Though being cruel and merciless in the battlefields, the total obedience to the command hierarchy makes message delivering between Stormtroopers quite inefficient, which finally caused the escape of Luke Skywalker, the destroy of the Death Star, and the collapse of the Galactic Empire.
In particular, the hierarchy of Stormtroopers is defined by a binary tree. Everyone in the tree has at most two direct subordinates and exactly one direct leader, except the first (numbered 1) Stormtrooper, who only obey the order of the Emperor.
It has been a time-consuming task for the Stormtroopers to input messages into his own log system. Suppose that the i-th Stormtrooper has a message of length ai, which means that it costs ai time to input this message into a log system. Everyone in the hierarchy has the mission of collecting all messages from his subordinates (a direct or indirect children in the tree) and input thses messages and his own message into his own log system.
Everyone in the hierarchy wants to optimize the process of inputting. First of all, everyone collects the messages from all his subordinates. For a Stormtrooper, starting from time 0, choose a message and input it into the log system. This process proceeds until all messages from his subordinates and his own message have been input into the log system. If a message is input at time t, it will induce t units of penalty.
For every Stormtrooper in the tree, you should find the minimum penalty.
Input
The first line of the input contains an integer T, denoting the number of test cases.
In each case, there are a number n (1≤n≤105) in the first line, denoting the size of the tree.
The next line contains n integers, the i-th integer denotes ai (0≤ai≤108), the i-th Stormtrooper’s message length.
The following n−1 lines describe the edges of the tree. Each line contains two integers u,v (1≤u,v≤n), denoting there is an edge connecting u and v.
Output
For each test case, output n space-separated integers in a line representing the answer. i-th number is the minimum penalty of gathering messages for i-th Stormtrooper.
Sample Input
1
3
1 2 3
1 2
2 3
Sample Output
10 7 3
