← 返回题目列表

Codeforces · 1842/F

F. 丹增和树

中文机器翻译题面 查看原题

Tenzing 有一个由 $$$n$$$ 个顶点组成的无向树。

按以下方式定义具有黑色和白色顶点的树的值。边的值是删除该边后树的两个分量中黑色节点的数量之间的绝对差。树的值是所有边上的值的总和。

对于所有$$$k$$$,使得$$$0 \leq k \leq n$$$,Tenzing 想知道当 $$$k$$$ 顶点被涂成黑色并且 $$$n-k$$$ 顶点被涂成白色时树的最大值。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 5000$$$) — 顶点数。

输入的以下 $$$n-1$$$ 行包含 $$$2$$$ 整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$) - 表示顶点 $$$u_i$$$ 和 $$$u_i$$$ 之间的边$$$v_i$$$。保证给定的边形成一棵树。

输出

输出 $$$n+1$$$ 数字。第 $$$i$$$ 个数字是 $$$k=i-1$$$ 的答案。

示例

输入 #1

4
1 2
3 2
2 4

输出 #1

0 3 4 5 6

输入 #2

1

输出 #2

0 0

注意

考虑第一个例子。当$$$k=2$$$时,Tenzing可以将顶点$$$1$$$和$$$2$$$涂成黑色,则边$$$(1,2)$$$的值为0,其他边的值都等于$$$2$$$。所以那棵树的价值是$$$4$$$。