Remove Bridges
Contest: Educational Codeforces Round 166 (Rated for Div. 2)
Difficulty rating: 2800
Tags: data structures, dfs and similar, dp, greedy, sortings, trees

You are given a rooted tree, consisting of $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Vertex $$$1$$$ is the root. Additionally, the root only has one child.

You are asked to add exactly $$$k$$$ edges to the tree (possibly, multiple edges and/or edges already existing in the tree).

Recall that a bridge is such an edge that, after you remove it, the number of connected components in the graph increases. So, initially, all edges of the tree are bridges.

After $$$k$$$ edges are added, some original edges of the tree are still bridges and some are not anymore. You want to satisfy two conditions:

- for every bridge, all tree edges in the subtree of the lower vertex of that bridge should also be bridges;
- the number of bridges is as small as possible.

Solve the task for all values of $$$k$$$ from $$$1$$$ to $$$n - 1$$$ and output the smallest number of bridges.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of vertices of the tree.

Each of the next $$$n - 1$$$ lines contain two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the description of the edges of the tree. It's guaranteed that the given edges form a valid tree.

Additional constraint on the input: the root (vertex $$$1$$$) has exactly one child.

The sum of $$$n$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each testcase, print $$$n - 1$$$ integers. For each $$$k$$$ from $$$1$$$ to $$$n - 1$$$ print the smallest number of bridges that can be left after you add $$$k$$$ edges to the tree.

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

Example input:
4
2
1 2
12
4 10
5 12
12 11
3 6
9 6
1 6
12 7
11 6
2 11
10 9
10 8
8
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5
1 2
2 3
3 4
4 5

Example output:
0 
7 3 1 0 0 0 0 0 0 0 0 
4 1 0 0 0 0 0 
0 0 0 0

Editorial:
What does an extra edge change in the configuration of the bridges? Well, all tree edges on the path between the two vertices that an extra edge connects, stop being bridges.
So, the task can be restated as follows: choose $$$k$$$ pairs of distinct vertices such that:
• a root is present in at least one pair;
• the number of edges in the union of the paths between the vertices of all pairs is as large as possible;
• there is no vertex covered by at least one path such that an edge to its parent is not a part of any path.
The next idea is quite intuitive. It only makes sense to choose a root or the leaves of the tree into the pairs. If any pair has a non-leaf vertex, you can safely prolong the path until any of the leaves in its subtree, and the union of the paths will not become smaller.
Now for the tricky idea. Instead of choosing $$$k$$$ pairs of root/leaves, you can actually just take a root and $$$2k - 1$$$ leaves, and there will always be a way to split them into pairs to satisfy all conditions.
Let's show that. Traverse the tree with a DFS and record the order you visit the leaves. Pair up a root with the middle leaf in that order. Then pair up leaves $$$1$$$ and $$$2k-1$$$, $$$2$$$ and $$$2k-2$$$ and so on. This way, the path for every pair includes a vertex on the path of the first pair (the one that includes the root). Thus, the union of the paths is the same as the union of all vertical paths from the leaves to the root. That obviously satisfies the condition on the connectedness of the bridges.
Notice how that union of the paths is also the largest possible on that set of leaves. Every path between the leaves can be viewed at as two vertical paths from each leaf. The longest vertical path from each leaf is the one going to the root. And we have exactly the union of these vertical paths as our solution.
Thus, the task actually becomes as follows: choose $$$2k - 1$$$ leaves in such a way that the union of their paths to the root is as large as possible.
That can actually be done greedily. Take a leaf with the longest path to the root. Then keep taking leaves that add as many new edges into the union as possible.
That idea can be implemented as follows. For every vertex, calculate the longest path that starts in it and ends in some leaf. Can be done with a single DFS. Maintain a set of all vertices sorted by their longest paths. On each step, take a vertex with the largest value and remove all vertices on that path (any path of the maximum length if there are multiple) from the set.
Overall complexity: $$$O(n \log n)$$$ per testcase.