# [ICPC2024 Xi'an I] Fix the Tree

## 题目描述

You are given a tree consisting of \$n\$ vertices. Each vertex \$i\$ of this tree has a value \$w_i\$ assigned to it. Now the vertex \$u\$ will be broken. Once it's broken, vertex \$u\$ and all edges with one end at vertex \$u\$ will be removed from the tree. To make the tree connected, you can do the following operation any number of times(possibly zero) in any order: - First choose two vertices \$u\$ and \$v\$ from the tree; - Then pay \$w_u+w_v\$ coins, and add an edge between vertices \$u\$ and \$v\$; - At last, replace \$w_u+1\$ with \$w_u\$, replace \$w_v+1\$ with \$w_v\$. Your task is to calculate the minimum number of coins to be paid. But you don't know which vertex \$u\$ is, so you need to find the answer for each \$1\le u\le n\$. Please answer all the queries independently.

## 输入输出格式

### 输入格式

The first line contains a single integer \$n(2\le n\le 10^6)\$ --- the number of vertices in this tree. The next line contains \$n\$ numbers, the \$i\$ -th number is \$w_i(1\le w_i\le n)\$. The next \$n-1\$ lines contain a description of the tree's edges. The \$i\$ -th of these lines contains two integers \$u_i\$ and \$v_i(1\le u_i,v_i\le n) \$ --- the numbers of vertices connected by the \$i\$ -th edge. It is guaranteed that the given edges form a tree.

### 输出格式

Print \$n\$ integers, the \$i\$ -th integer is the answer when \$u=i\$.

## 输入输出样例

### 输入样例 #1

``````6
1 1 1 1 1 1
1 2
1 3
1 4
2 5
2 6``````

### 输出样例 #1

``4 4 0 0 0 0``

### 输入样例 #2

``````4
1 2 3 4
1 2
1 3
1 4``````

### 输出样例 #2

``12 0 0 0``

### 输入样例 #3

``````7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7``````

### 输出样例 #3

``5 12 16 0 0 0 0``