CF1646D.Weight the Tree

You are given a tree of $n$ vertices numbered from $1$ to $n$. A tree is a connected undirected graph without cycles.

For each $i=1,2, \ldots, n$, let $w_i$ be the weight of the $i$-th vertex. A vertex is called good if its weight is equal to the sum of the weights of all its neighbors.

Initially, the weights of all nodes are unassigned. Assign positive integer weights to each vertex of the tree, such that the number of good vertices in the tree is maximized. If there are multiple ways to do it, you have to find one that minimizes the sum of weights of all vertices in the tree.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。树是一种无环的连通无向图。

对每个 $i = 1, 2, \ldots, n$，令 $w_i$ 表示第 $i$ 个顶点的权值。若一个顶点的权值等于其所有邻接顶点的权值之和，则称该顶点为好顶点。

初始时，所有顶点的权值均未赋值。请为树的每个顶点赋予正整数权值，使得树中好顶点的数量最大化。若存在多种方案能达到最大好顶点数量，则需在其中选出一种使得所有顶点权值之和最小的方案。

The first line contains one integer $n$ ($2\le n\le 2\cdot 10^5$) — the number of vertices in the tree.

Then, $n−1$ lines follow. Each of them contains two integers $u$ and $v$ ($1\le u,v\le n$) denoting an edge between vertices $u$ and $v$. It is guaranteed that the edges form a tree.

第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$）——树中顶点的数量。

接下来是 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1\le u,v\le n$），表示顶点 $u$ 与顶点 $v$ 之间的一条边。保证这些边构成一棵树。

In the first line print two integers — the maximum number of good vertices and the minimum possible sum of weights for that maximum.

In the second line print $n$ integers $w_1, w_2, \ldots, w_n$ ($1\le w_i\le 10^9$) — the corresponding weight assigned to each vertex. It can be proven that there exists an optimal solution satisfying these constraints.

If there are multiple optimal solutions, you may print any.

第一行输出两个整数——好顶点的最大数量，以及达到该最大数量时权重和的最小可能值。

第二行输出 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1\le w_i\le 10^9$）——分别赋给每个顶点的对应权重。可以证明存在满足这些约束的最优解。

若存在多个最优解，输出任意一个即可。

This is the tree for the first test case:

In this case, if you assign a weight of $1$ to each vertex, then the good vertices (which are painted black) are $1$, $3$ and $4$. It impossible to assign weights so that all vertices are good vertices. The minimum sum of weights in this case is $1+1+1+1=4$, and it is impossible to have a lower sum because the weights have to be positive integers.

This is the tree for the second test case:

In this case, if you assign a weight of $1$ to each vertex, then the good vertices (which are painted black) are $2$ and $3$. It can be proven that this is an optimal assignment.

这是第一个测试用例的树：

本例中，若为每个顶点赋予权值 $1$，则好顶点（涂成黑色的顶点）为 $1$、$3$ 和 $4$。不可能为顶点赋予权值使得所有顶点均为好顶点。本例中权值之和的最小值为 $1+1+1+1=4$；由于权值必须为正整数，因此无法得到更小的和。

这是第二个测试用例的树：

本例中，若为每个顶点赋予权值 $1$，则好顶点（涂成黑色的顶点）为 $2$ 和 $3$。可以证明该赋权方案是最优的。