You Are Given a Tree
Contest: Codeforces Round 507 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 2800
Tags: data structures, dp, trees

A tree is an undirected graph with exactly one simple path between each pair of vertices. We call a set of simple paths $$$k$$$-valid if each vertex of the tree belongs to no more than one of these paths (including endpoints) and each path consists of exactly $$$k$$$ vertices.

You are given a tree with $$$n$$$ vertices. For each $$$k$$$ from $$$1$$$ to $$$n$$$ inclusive find what is the maximum possible size of a $$$k$$$-valid set of simple paths.

Input format:
The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of vertices in the tree.

Then following $$$n - 1$$$ lines describe the tree, each of them contains two integers $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$) — endpoints of the corresponding edge.

It is guaranteed, that the given graph is a tree.

Output format:
Output $$$n$$$ numbers, the $$$i$$$-th of which is the maximum possible number of paths in an $$$i$$$-valid set of paths.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
One way to achieve the optimal number of paths for the second sample is illustrated in the following picture:

Example input:
7
1 2
2 3
3 4
4 5
5 6
6 7

Example output:
7
3
2
1
1
1
1

Example input:
6
1 2
2 3
2 4
1 5
5 6

Example output:
6
2
2
1
1
0

Editorial:
Let's examine a solution in $$$O(n^2)$$$ first.
Introudce a dynamic programming on subtree, the dp of the vertex is the number of paths, which can be taken from the subtree and the maximum length of incomplete path, which ends exactly in vertex v.
Notice that this dp can be maximised as pair — the more of complete paths than better, and if the number of complete paths coincides, then it's better to have the incomplete path as long as possible.
This dp allows to get an answer in $$$O(n)$$$ for a single $$$k$$$
How to calculate this dp for a vertex? We need to sum the number of complete paths over all children and also either take one of the incomplete path of children and attach the current vertex to it or try to form a new path from two longest incomplete paths of children.
It is possible to use $$$O(n^2)$$$ solution to get $$$O(n \sqrt(n) log)$$$ solution.
Notice, that $$$f(k) \le \frac{n}{k}$$$. From this we get, that $$$f$$$ takes no more than $$$O(\sqrt(n))$$$ values. Indeed, there are values $$$f(1), f(2), \ldots f(\sqrt(n))$$$ and for all $$$m \ge \sqrt{n} f(m) \le \sqrt{n}$$$.
To find the corresponding bounds we can use binary search — this way we get solution in $$$O(n \sqrt(n) log)$$$.
This is already enough to get Accepted on codeforces, however I want to share some more insights about faster, $$$O(n \log^2(n))$$$ solution, it wasn't required to get OK, mostly because we found out that writing this solution is really complicated and making it work faster then sqrt-log solution is even more harder.
The funny thing is that we can do a dynamic programming for all $$$k$$$ from $$$1$$$ to $$$n$$$ simultaneously.
In fact, we will use cartesian tree (more precisely, it is better to have segment tree for efficiency).
We will return from subtree of vertex $$$v$$$ structure of size size[v], containing the dp values for all $$$k$$$ from $$$1$$$ to size[v], where $$$size$$$ — it the size of the subtree.
So we need to be able to merge results from subtrees. In particular, from the subtree dp's of sizes $$$s_1, \ldots, s_t$$$ ($$$s_1 \ge s_2 \ge \ldots \ge s_t$$$) we want to get $$$\sum s_i$$$.
Let's take the result corresponding to $$$s_1$$$ as a basis, new-borned end can be appended naively. Also, more or less naively we can make the merge of prefix part of length $$$s_2$$$ (because this work "is paid" by the fact that we will not return the dp structure of size $$$s_2$$$).
So we have to deal with a part from $$$s_2$$$ to $$$s_1$$$.
In the structure we store pairs of numbers — how much complete paths, and the length of the incomplete path. Note that there are two types of relaxation — when we increase the number of complete paths and when we simply relax the length of incomplete path.
Notice, that $$$f(k) \le \frac{n}{k}$$$, and hence $$$\sum f(k) = O(n \log(n))$$$. This way the number of transitions of first type is small and we can perform them naively, we just need to find all such transitions fast. We can maintain in the above mentioned data structure maximums on the segments and fast pull all such transitions.
Other transitions can be handled with max= on a suffix and +1 on the whole data structure, the latter we store together with the instance of data structures and handle them when we merge one data structure into the other.
The overall complexity is $$$O(n \log^2)$$$.