附加文件

题目描述

五个代表甲乙丙丁戊在种一棵树。 已知这棵树由 $n$ 个点组成，每个点有权重 $w_i$，以及到树根的距离 $d_i$。规定 $d_1=0$。

• 甲说：“我厌恶点对 $(i,j)$ 满足 $i$ 是 $j$ 的祖先且 $w_i > w_j$”
• 乙说：“我厌恶点对 $(i,j)$ 满足 $i$ 是 $j$ 的祖先且 $w_i < w_j$”
• 丙说：“我厌恶点对 $(i,j)$ 满足 $i < j$ 且 $i,j$ 均不是另一个点的祖先”
• 丁说：“我厌恶点距离根太远”
• 戊什么都没说

现在甲丙丁选择点集 $A$，乙戊选择 $A$ 的补集 $B$。

规定点集 $X$ 的厌恶值为 $D(X)$，二元运算 $x \circ y$ 表示 $x$ 是否被 $y$ 所厌恶，则有：

$$D(A) = \sum_{i \in A} \sum_{j \in A} [(i, j) \circ \text{甲} \lor (i, j) \circ \text{丙}] + \sum_{i \in A} d_i$$$$D(B) = \sum_{i \in B} \sum_{j \in B} [(i, j) \circ \text{乙}]$$

现在要你对于 $|B|=0, 1, \dots, n$ 依次输出 $D(A)+D(B)$ 的最小值。

输入格式

第一行为一个整数 $n$，表示点数。

第二行几个整数 $w_i$，表示每个树节点的权重。

接下来 $n-1$ 行每行两个整数 $u,v$ 表示一条树边。

输出格式

共 $n+1$ 行，第 $i$ 行一个整数，表示当 $|B|=i-1$ 时 $D(A)+D(B)$ 的最小值。

样例

样例输入 1

4
4 1 2 3
1 2
2 3
2 4

样例输出 1

9
5
2
1
2

数据范围与约定

对于 $100\%$ 的数据范围，$1\le n,w_i\le 5\times 10^5$。

每个测试包的详细限制如下：

测试包编号	$n$	特殊性质	分值
1	$\le 20$	无	12
2	$\le 100$		3
3	$\le 5000$		6
4	$\le 5 \times 10^5$	$d_i=[i>1]$	10
5		$w_i=1$	12
6		$d_i=i-1$	14
7		无	43