题目描述

昨天表白失败，属实有点破防。

小 Z 正在表白小 W，他们之间的关系可以看作是一棵有根树，根是 $1$。每个点要么属于小 Z，要么属于小 W，可以用一个长度为 $n$ 的 $01$ 序列表示：第 $i$ 个数为 $1$ 表示点 $i$ 属于小 Z，为 $0$ 表示属于小 W。

定义小 Z 向小 W 表白次数为：点对 $(x,y)$ 的个数，满足 $x$ 是 $y$ 的祖先，并且点 $x$ 属于小 Z、点 $y$ 属于小 W。

为了尽可能减少表白次数，你可以翻转至多 $k$ 个节点（把某个属于小 Z 的点变成小 W，或把小 W 变成小 Z），使表白次数最小。

你需要回答 $k=0,1,\ldots,n$ 的所有情况的答案。

输入格式

第一行一个正整数 $n$。
第二行一个长度为 $n$ 的 $01$ 序列。
接下来 $n-1$ 行每行两个正整数 $x,y$，表示树上的一条边 $(x,y)$。

输出格式

一行 $n+1$ 个数，第 $i$ 个数表示 $k=i-1$ 时的答案。

8
1 1 1 0 1 0 1 0
7 3
1 4
5 1
7 5
6 7
2 6
2 8

8 4 1 0 0 0 0 0 0

10
0 1 0 0 1 1 1 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

14 9 6 2 0 0 0 0 0 0 0

样例解释

对于样例 1：

• $k=1$ 时，将 $8$ 号点变成 $1$。
• $k=2$ 时，将 $6,8$ 号点变成 $1$。
• $k=3$ 时，将 $4,6,8$ 号点变成 $1$。

数据范围与提示

• 特殊性质 A：保证 $01$ 序列最多含有 $10$ 个 $1$。
• 特殊性质 B：保证树是一条以 $1$ 为端点的链。