Leaf Sets
Contest: Codeforces Round 510 (Div. 2)
Difficulty rating: 2400
Tags: data structures, dfs and similar, dsu, graphs, greedy, sortings, trees

You are given an undirected tree, consisting of $$$n$$$ vertices.

The vertex is called a leaf if it has exactly one vertex adjacent to it.

The distance between some pair of vertices is the number of edges in the shortest path between them.

Let's call some set of leaves beautiful if the maximum distance between any pair of leaves in it is less or equal to $$$k$$$.

You want to split all leaves into non-intersecting beautiful sets. What is the minimal number of sets in such a split?

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le k \le 10^6$$$) — the number of vertices in the tree and the maximum distance between any pair of leaves in each beautiful set.

Each of the next $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the description of the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

Output format:
Print a single integer — the minimal number of beautiful sets the split can have.

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

Note:
Here is the graph for the first example:

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

Example output:
2

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

Example output:
2

Editorial:
Let's use the following technique, which is pretty common for tree problems. Let the root of the tree be some none-leaf vertex. Run dfs from the root and let the vertex yield all the resulting sets in the optimal answer for its subtree. For each vertex you iterate over its children and merge the yielded sets.
The first thing to notice is that you only need the deepest vertex from each set to check its mergeability. Let's call the distance between the vertex $$$v$$$ and the deepest vertex in some set $$$u$$$ in its subtree $$$d_u$$$. Now two sets $$$a$$$ and $$$b$$$ can be merged only if $$$d_a + d_b \le k$$$. Moreover, $$$d$$$ value of the resulting the set is $$$max(d_a, d_b)$$$.
The time has come to reveal the merging process. We will heavily rely on a fact that the resulting $$$d$$$ doesn't change after merging. Let's merge the sets with the smallest $$$d$$$ to any other possible sets.
Now we can deduce the small-to-large solution from it. Let the vertex yield the whole multiset of the depths of the resulting sets. Now take the child with the largest number of resulting sets and add all the values from the other children to its multiset. Then merge the maximum possible number of sets and yield the result. The size of set yielded by the root is the answer.
The complexity of this solution is $$$O(n \cdot log^2{n})$$$, which still can be too slow.
You can notice that if you have a pair of sets $$$a$$$ and $$$b$$$ such that $$$d_a \le d_b, d_a + d_b > k$$$, set $$$b$$$ will never affect the answer. If some set $$$c$$$ could later be merged with $$$b$$$, it can be with $$$a$$$ as well. Thus, you can erase set $$$b$$$ from the result and add $$$1$$$ to the answer. Then the vertex will always yield a single set. The solution mentioned above works in $$$O(n \log n)$$$ with this modification.
This can later be modified a bit to a $$$O(n)$$$ solution but that is totally unnecessary and works about the same time as $$$O(n \log n)$$$. It still takes most of the time to read the input.