编程介的小学生 2017-10-28 02:55 采纳率: 20.5%
浏览 785
已采纳

Army Formations

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

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-11-15 15:47
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择
  • ¥15 这款软件是什么?需要能满足我的需求
  • ¥15 SpringSecurityOauth2登陆前后request不一致