COCI 2019/2020 - Olympiad - Pastiri

View as PDF

Submit solution

Points: 1.10 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Olympiad
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

"Tôi chưa bao giờ cảm thấy no tới nỗi không thể ăn thêm một con cừu" - Mr. Malnar

Một đàn ~K~ con cừu sống trên một cây - một đồ thị liên thông không chứa chu trình. Cây gồm ~N~ đỉnh được đánh số bằng các số nguyên từ ~1~ tới ~N~. Mỗi đỉnh trên cây là nhà của tối đa một chú cừu. Một người chăn cừu thông thái đã nhận ra rằng, sớm hay muộn thì các con chó sói cũng sẽ biết trèo cây.

Để bảo vệ các chú cừu, bạn cần đặt các người chăn cừu vào một số đỉnh sao cho mỗi chú cừu đều được bảo vệ bởi ít nhất một người chăn cừu. Điều mà ai cũng biết chính là mỗi người chăn cừu sẽ và chỉ bảo vệ tất cả các chú cừu mà gần nhất với họ. Khoảng cách giữa một chú cừu và một người chăn cừu bất kì đúng bằng với số đỉnh trên đường đi duy nhất giữa đỉnh chứa chú cừu và đỉnh chứa người chăn cừu (bao gồm cả hai đỉnh đó). Hơn nữa, một người chăn cừu có thể ở cùng một đỉnh với một chú cừu. Và đương nhiên, trong trường hợp đó, anh ấy sẽ chỉ bảo vệ chú cừu đó.

Hãy xác định số lượng người chăn cừu tối thiểu cần đặt vào các đỉnh trên cây sao cho mỗi chú cừu được bảo vệ bởi ít nhất một người chăn cừu. Ngoài ra, hãy xác định một cách sắp xếp số lượng người chăn cừu tối thiểu thỏa mãn đề bài.

Input

Dòng đầu tiên gồm các số nguyên ~N~ và ~K\,(1 \le K \le N)~.

~N - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~a_i~ và ~b_i~ thể hiện một cạnh vô hướng giữa đỉnh ~a_i~ và đỉnh ~b_i~.

Dòng tiếp theo gồm ~K~ số nguyên ~o_i\,(1 \le o_i \le N)~ phân biệt thể hiện các đỉnh có chứa một chú cừu.

Output

Dòng đầu tiên in ra một số nguyên ~X~ thể hiện số người chăn cừu tối thiểu thỏa mãn đề bài.

Dòng thứ hai in ra ~X~ số nguyên cách nhau bởi một dấu cách thể hiện các đỉnh chứa các người chăn cừu.

Nếu có nhiều đáp án đúng, hãy in ra một trong số chúng.

Sample 1

Input
4 2
1 2
2 3
3 4
1 4
Output
2
1 3

Sample 2

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

Sample 3

Input
20 9
1 2
2 3
2 4
4 5
4 6
5 7
7 8
8 9
7 10
10 11
6 12
6 13
6 17
13 14
14 15
14 16
17 18
18 19
18 20
1 3 9 11 12 15 16 19 20
Output
3
5 14 18

Giải thích test mẫu 3:

img

Ràng buộc

  • ~4~ test đầu tiên thỏa mãn ~1 \le N \le 100\,000~, mỗi đỉnh ~x = 1,\ldots,n - 1~ đều nối với đỉnh ~x + 1~.
  • ~6~ test tiếp theo thỏa mãn ~1 \le K \le 15~, ~1 \le N \le 500\,000~.
  • ~15~ test tiếp theo thỏa mãn ~1 \le N \le 2\,000~.
  • ~22~ test còn lại thỏa mãn ~1 \le N \le 500\,000~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.