시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 82 | 40 | 31 | 47.692% |
You are given a tree T and an integer K. You can choose arbitrary distinct two vertices u and v on T. Let P be the simple path between u and v. Then, remove vertices in P, and edges such that one or both of its end vertices is in P from T. Your task is to choose u and v to maximize the number of connected components with K or more vertices of T after that operation.
The input consists of a single test case formatted as follows.
N K u1 v1 . . . uN-1 vN-1
The first line consists of two integers N, K (2 ≤ N ≤ 100,000, 1 ≤ K ≤ N). The following N-1 lines represent the information of edges. The (i+1)-th line consists of two integers ui, vi (1 ≤ ui, vi ≤ N and ui ≠ vi for each i). Each {ui, vi} is an edge of T. It's guaranteed that these edges form a tree.
Print the maximum number of connected components with K or more vertices in one line.
2 1 1 2
0
7 3 1 2 2 3 3 4 4 5 5 6 6 7
1
12 2 1 2 2 3 3 4 4 5 3 6 6 7 7 8 8 9 6 10 10 11 11 12
4
3 1 1 2 2 3
1
3 2 1 2 2 3
0
9 3 1 2 1 3 1 4 4 5 4 6 4 7 7 8 7 9
2