시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 138 | 36 | 23 | 20.000% |
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$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 \ne 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$.
2 1 1 2
1
2 3 1 2
2
5 10 1 2 2 3 3 4 4 5
3
ICPC > Regionals > North America > Southeast USA Regional > 2020 Southeast USA Regional Programming Contest H번
ICPC > Regionals > North America > Pacific Northwest Regional > 2020 ICPC Pacific Northwest Region > Division 1 L번
ICPC > Regionals > North America > Mid-Atlantic Regional > 2020 Mid-Atlantic USA Regional Contest K번
ICPC > Regionals > North America > South Central USA Regional > 2020 South Central USA Regional Contest H번