CF1842F Tenzing and Tree

Tenzing 有一棵包含 $n$ 个顶点的无向树。 对于一棵顶点被染成黑色和白色的树，定义其价值如下：对于树中的一条边，其价值为删除该边后，树被分成的两个连通块中黑色节点数的绝对差。树的总价值为所有边的价值之和。 对于所有 $k$ 满足 $0 \leq k \leq n$，Tenzing 想知道当有 $k$ 个顶点被染成黑色、$n-k$ 个顶点被染成白色时，这棵树的最大价值是多少。

输入的第一行包含一个整数 $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$ 之间有一条边。保证给定的边构成一棵树。

输出 $n+1$ 个数字，第 $i$ 个数字表示 $k=i-1$ 时的答案。

考虑第一个样例。当 $k=2$ 时，Tenzing 可以将顶点 $1$ 和 $2$ 染成黑色，此时边 $(1,2)$ 的价值为 $0$，其他边的价值均为 $2$。所以该树的总价值为 $4$。 由 ChatGPT 4.1 翻译