Weight the Tree
Contest: Codeforces Round 774 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, dfs and similar, dp, implementation, trees

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
This is the tree for the first test case:

This is the tree for the second test case:

Example input:
4
1 2
2 3
2 4

Example output:
3 4
1 1 1 1

Example input:
3
1 2
1 3

Example output:
2 3
1 1 1

Editorial:
If $$$n=2$$$, we can assign $$$w_1=1$$$ and $$$w_2=1$$$ and there is no way to get a better answer because all vertices are good and the sum of weights cannot be smaller because the weights have to be positive.
If $$$n>2$$$, two vertices sharing an edge cannot be both good. To prove this, we are going to analyze two cases. If the two vertices have distinct weights, then the one with a smaller weight cannot be good, because the one with a larger weight is its neighbor. Otherwise, if both vertices have the same weight, then none of them can have another neighbor, as that would increase the sum of their neighbors by at least $$$1$$$. So, the only way this could happen is if $$$n=2$$$, but we are assuming that $$$n>2$$$.
Thus, the set of good vertices must be an independent set. We will see that for each independent set of vertices in the tree, there is an assignment of weights where all the vertices from this set are good. We can assign a weight of $$$1$$$ to each vertex that is not in the set, and assign its degree to each vertex in the set. Because all neighbors of a vertex in the set are not in the set, then all of them have a weight of $$$1$$$ and this vertex is good.
Therefore, the maximum number of good vertices is the same as the maximum size of an independent set in this tree. For a fixed independent set of the maximum size, the construction above leads to a configuration with the minimum sum of weights. This is because all vertices must have a weight of at least $$$1$$$, and the vertices in the set must have a weight of at least its degree.
So, to solve the problem it is enough to root the tree in an arbitrary vertex and solve a tree dp. Let's call $$$f(x, b)$$$ to the pair $$$(g, s)$$$, where $$$g$$$ is the maximum number of good vertices in the subtree of vertex $$$x$$$ assuming that $$$x$$$ is good (if $$$b=1$$$) or that it is not good (if $$$b=0$$$), and $$$s$$$ is the minimum sum of weights for that value $$$g$$$.
The values of $$$f(x,b)$$$ can be computed with a dp, using the values of $$$f$$$ in the children of node $$$x$$$. If $$$b=1$$$, then for each child $$$c$$$ you must sum $$$f(c,0)$$$. If $$$b=0$$$, for each child $$$c$$$ you can choose the best answer between $$$f(c,0)$$$ and $$$f(c,1)$$$. The answer to the problem will be the best between $$$f(\text{root},0)$$$ and $$$f(\text{root},1)$$$
To construct the assignment of weights, you can do it recursively considering for each vertex if it has to be good or not, in order to keep the current value of the answer. In case both options (making it good or not) work, you have to choose to not make it good, as you do not know if its father was good or not.
Intended complexity: $$$\mathcal{O}(n)$$$