题目描述

有一棵 $n$ 个点的树，需要把其中 $k$ 个点染成黑色，每条边都有权值，定义一条边的权值为这条边两侧黑点数量的差的绝对值，一棵树的权值是所有边的权值之和。

对于所有的 $k$ 满足$0 \leqslant k \leqslant n$,输出一个整数，表示染色 $k$ 个点后，整棵树的最大权值。

输入格式

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

接下来 $n-1$ 行，每行两个正整数 $u,v \,\, (1 \leqslant u,v \leqslant n)$ 表示 $u$ 到 $v$ 有一条边。

输出格式

输出 $n+1$ 个正整数，表示答案。

4
1 2
3 2
2 4

0 3 4 5 6

1

0 0

提示

$100\%$ 的数据，$1 \leqslant n \leqslant 5000$ 。