310495: CF1842F. Tenzing and Tree
Description
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.
InputThe 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.
OutputOutput $n+1$ numbers. The $i$-th number is the answer of $k=i-1$.
ExamplesInput4 1 2 3 2 2 4Output
0 3 4 5 6Input
1Output
0 0Note
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$.
Input
题意翻译
有一棵 $n$ 个点的树，其中有 $k$ 个点被染上了黑色。 每条边都有权值，定义一条边的权值为这条边**两侧黑点数量**的差的**绝对值**。 一棵树的权值是所有边的权值之和。 对于 $\forall k$ 满足 $0\le k\le n$，你需要确定这 $k$ 个点，满足在染色后，这棵树的权值最大。 $n\le 5000$。Output
F. Tenzing and Tree
**题设：**
给定一个无向树，包含n个顶点。
**定义：**
定义树中黑顶点和白顶点的“价值”。一个边的“价值”是在删除该边后，树的两个组件中黑节点数量的绝对差。整棵树的价值是所有边的价值之和。
**任务：**
对于所有满足0 ≤ k ≤ n的k，计算出当k个顶点被涂成黑色，n-k个顶点被涂成白色时，树的最大价值。
**输入数据格式：**
第一行输入一个整数n（1≤n≤5000）——顶点的数量。
接下来的n-1行，每行输入2个整数u_i和v_i（1 ≤ u_i, v_i ≤ n, u_i ≠ v_i），表示顶点u_i和v_i之间有一条边。保证给定的边构成一棵树。
**输出数据格式：**
输出n+1个数。第i个数是k=i-1时的答案。
**示例：**
输入
```
4
1 2
3 2
2 4
```
输出
```
0 3 4 5 6
```
**注意：**
在第一个示例中，当k=2时，Tenzing可以将顶点1和2涂成黑色，那么边(1,2)的价值是0，其他边的价值都是2。所以那棵树的价值是4。**题目大意：** F. Tenzing and Tree **题设：** 给定一个无向树，包含n个顶点。 **定义：** 定义树中黑顶点和白顶点的“价值”。一个边的“价值”是在删除该边后，树的两个组件中黑节点数量的绝对差。整棵树的价值是所有边的价值之和。 **任务：** 对于所有满足0 ≤ k ≤ n的k，计算出当k个顶点被涂成黑色，n-k个顶点被涂成白色时，树的最大价值。 **输入数据格式：** 第一行输入一个整数n（1≤n≤5000）——顶点的数量。 接下来的n-1行，每行输入2个整数u_i和v_i（1 ≤ u_i, v_i ≤ n, u_i ≠ v_i），表示顶点u_i和v_i之间有一条边。保证给定的边构成一棵树。 **输出数据格式：** 输出n+1个数。第i个数是k=i-1时的答案。 **示例：** 输入 ``` 4 1 2 3 2 2 4 ``` 输出 ``` 0 3 4 5 6 ``` **注意：** 在第一个示例中，当k=2时，Tenzing可以将顶点1和2涂成黑色，那么边(1,2)的价值是0，其他边的价值都是2。所以那棵树的价值是4。