Kth Subtree

You are given an unrooted labeled tree. A subtree is a connected subgraph of this tree. The size of a subtree is the number of nodes in the subtree. Two subtrees are different if there is at least one node which is in one but not the other. The largest subtree is the original tree itself.

Compute the size of the $K^\mathrm {th}$ smallest non-empty subtree.


The first line of input contains two integers $n$ ($1 \le n \le 5\, 000$) and $K$ ($1 \le K \le 10^{18}$), where $n$ is the number of nodes in the tree, and you’re looking for the size of the $K^{th}$ smallest subtree. The nodes are numbered $1$ through $n$.

Each of the next $n-1$ lines contains a pair of integers $u$ and $v$ ($1 \le u, v \le n, u \neq v$), which represents an undirected edge between nodes $u$ and $v$. All edges are distinct. It is guaranteed that the edges form a single tree.


Output a single integer, which is the number of nodes in the $K^{th}$ smallest non-empty subtree of the input tree. If there are fewer than $K$ non-empty subtrees of the given tree, output $-1$.

Sample Input 1 Sample Output 1
2 1
1 2
Sample Input 2 Sample Output 2
2 3
1 2
Sample Input 3 Sample Output 3
5 10
1 2
2 3
3 4
4 5
CPU Time limit 1 second
Memory limit 2048 MB
Source 2020 ICPC North America Regionals (March 6 2021)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in