Tree Journey

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Bob is making a journey on a tree with n nodes and n-1 edges. The nodes are numbered from 1 to n, and there is exactly one simple path between any two nodes. Bob starts his journey from node 1. Each step, Bob can move from his current node to an adjacent node. If Bob travels on the same edge twice, it will take him two steps. Due to his busy schedule, Bob can only move up to K steps. Your task is to find the maximum number of distinct nodes Bob can visit during his journey.

Input Specification

The first line contains two integers n and K (2 \leq n \leq 10^5, 1 \leq K \leq 10^9), representing the number of nodes in the tree and the maximum number of steps Bob can take, respectively.

Each of the next n-1 lines contains two integers u and v (1 \leq u, v \leq n, u \neq v), indicating an edge between nodes u and v.

Output Specification

Output a single integer representing the maximum number of distinct nodes Bob can visit.

Constraints

Subtask Points Additional constraints
1 40 n \le 100, K \le 200
2 30 n \le 1\,000, K \le 2\,000
3 30 No additional constraints

Sample Input 1

5 2
2 1
3 2
4 3
5 4

Sample Output 1

3

Explanation

Bob can start from 1, move to 2, and finally stop at 3. He will visit 3 nodes in total.

Sample Input 2

9 8
1 2
1 3
2 4
2 9
4 6
4 8
3 5
3 7

Sample Output 2

6

Comments

There are no comments at the moment.