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$$$。