CF1842F.Tenzing and Tree

Tenzing has an undirected tree of $n$ vertices.

Define the value of a tree with black and white vertices in the following way. The value of an edge is the absolute difference between the number of black nodes in the two components of the tree after deleting the edge. The value of the tree is the sum of values over all edges.

For all $k$ such that $0 \leq k \leq n$, Tenzing wants to know the maximum value of the tree when $k$ vertices are painted black and $n-k$ vertices are painted white.

丹增有一棵包含 $n$ 个顶点的无向树。

定义一个具有黑白顶点的树的“值”如下：删除某条边后，树被分割为两个连通分量；该边的值等于这两个连通分量中黑色顶点数量之差的绝对值。整棵树的值定义为所有边的值之和。

对于所有满足 $0 \leq k \leq n$ 的 $k$，丹增想知道当恰好 $k$ 个顶点被染成黑色、其余 $n-k$ 个顶点被染成白色时，该树所能达到的最大值。

The first line of the input contains a single integer $n$ ($1\leq n\leq 5000$) — the number of vertices.

The following $n-1$ lines of the input contains $2$ integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n, u_i \neq v_i$) — indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

输入的第一行包含一个整数 $n$（$1\leq n\leq 5000$）—— 表示顶点的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$）—— 表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。保证所给的边构成一棵树。

Output $n+1$ numbers. The $i$-th number is the answer of $k=i-1$.

输出 $n+1$ 个数。其中第 $i$ 个数对应 $k=i-1$ 的答案。

Consider the first example. When $k=2$, Tenzing can paint vertices $1$ and $2$ black then the value of edge $(1,2)$ is 0, and the values of other edges are all equal to $2$. So the value of that tree is $4$.

考虑第一个例子。当 $k=2$ 时，Tenzing 可以将顶点 $1$ 和 $2$ 涂成黑色，此时边 $(1,2)$ 的值为 $0$，而其余各边的值均为 $2$。因此，该树的值为 $4$。