Birthday Party

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

Metabook, in its quest to be the app with the most features, has decided to add the option for a user to host a birthday party! On the user's birthday, they will have the option to invite everyone who has a closeness \le K to them.

Metabook is a social media platform modelled with N users as nodes. Users can be friended with other users, and this connection is bidirectional, with a_i,b_i denoting a friendship between user a_i and b_i. Additionally, these users and connections form a tree, and so the closeness between users A and B is the distance of the shortest path between them (which is also the only non-repeating path). For this problem, all users are numbered from 1 to N, and in this scenario user 1 is the one throwing the birthday party.


1\le N\le 10^5

1\le K\le N-1, 900

1\le a_i,b_i\le N

a_i\ne b_i

Input Specification

The first line contains two integers N and K, the number of users and the minimum closeness needed for a user to be invited

The next N-1 lines each contain two integers a_i and b_i, denoting a friendship between user a_i and b_i

Output Specification

The first line contains U, the number of users who will be invited

The second line contains U integers, the users who will be invited to user 1's birthday party, output in increasing order

Sample Input

7 1
1 2
2 3
1 5
3 4
2 6
1 7

Sample Output

2 5 7

Sample Explanation

Nodes 2, 5, and 7 all have a distance of 1 from node 1, so they will be invited.


There are no comments at the moment.