Description

给定一棵由 $n$ 个顶点组成的树。树中每个顶点 $i$ 都有一个值 $w_i$。

现在顶点 $u$ 将被破坏。一旦被破坏，顶点 $u$ 和所有以 $u$ 为一端的边将从树中移除。

为了使树重新连通，你可以执行以下操作任意次（可能为零次），顺序不限：

• 首先从树中选择两个顶点 $u$ 和 $v$；
• 然后支付 $w_u + w_v$ 个硬币，并在顶点 $u$ 和 $v$ 之间添加一条边；
• 最后，将 $w_u + 1$ 替换为 $w_u$，将 $w_v + 1$ 替换为 $w_v$。

你的任务是计算需要支付的最小硬币数。

但你不知道哪个顶点是 $u$，所以你需要为每个 $1 \le u \le n$ 找到答案。请独立回答所有查询。

Input Format

第一行包含一个整数 $n(2 \le n \le 10^6)$ —— 这棵树的顶点数。

接下来的一行包含 $n$ 个数，第 $i$ 个数是 $w_i(1 \le w_i \le n)$。

接下来的 $n-1$ 行包含树的边的描述。这些行中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i(1 \le u_i, v_i \le n)$ —— 由第 $i$ 条边连接的顶点的编号。

保证给定的边构成一棵树。

Output Format

输出 $n$ 个整数，第 $i$ 个整数是当 $u=i$ 时的答案。

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

4 4 0 0 0 0

4
1 2 3 4
1 2
1 3
1 4

12 0 0 0

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

5 12 16 0 0 0 0

Hint

给定一个有 $n$ 个点组成的树，每个点有一个权值 $w_i$。 点 $u$ 和相邻的边被删除。 你可以进行以下操作任意次数（可以为 $0$），让树重新成为连通图：

1. 选择两个点 $u$、$v$；
2. 花费 $w_u + w_v$ 的代价连接一条边 $(u,v)$；
3. $w_u \leftarrow w_u+1, w_v \leftarrow w_v+1$。

对于每个 $u$ 计算最小代价。（由 ChatGPT 4o 翻译）