1076 - Lộ trình từ thiện - AID
Tạo bởi: CLB Olympic Tin học HUTECH
Mô tả yêu cầu
CEO Nguyễn P. H đang là cái tên được nhắc nhiều nhất trên truyền thông và mạng xã hội những ngày gần đây, đặc biệt sau buổi livestream khủng thu hút tới hơn 400.000 lượt xem trực tiếp trên trang facebook cá nhân.
Nguyễn P. H một doanh nhân nổi tiếng ở Việt Nam. Hiện tại bà đang là Phó Chủ tịch Hội đồng quản trị và Tổng Giám đốc của Công ty Cổ phần Đ. N. Bên cạnh đó, mọi người cũng biết đến bà như một mạnh thường quân lớn. Sắp tới đây bà dự định sẽ đi chuyến về miền Trung để hỗ trợ cho đồng bào bị lũ lụt.
Ban quản lý của bà P. H đã liệt kê ra được danh sách gồm N - 1 địa điểm có thể đi đến được. Vị trí của bà H và N - 1 điểm trên được nối với nhau bằng các con đường do ban quản lý sắp xếp sẵn, tạo thành một đồ thị gồm N đỉnh liên thông, vô hướng, và không có chu trình.
Tuy nhiên do tình hình dịch bệnh, Chính phủ quy định chỉ được phép di chuyển tới không quá K địa điểm khác nhau, vì vậy bà H quyết định sẽ đến chính xác K địa điểm (bao gồm địa điểm của bà H) để làm từ thiện.
Ban quản lý sẽ đưa cho bạn nhiều bộ dữ liệu khác nhau. Với mỗi bộ dữ liệu bạn hãy giúp bà H chọn ra lộ trình ngắn nhất, xuất phát từ địa điểm 1 (vị trí của bà H) và đi qua chính xác K địa điểm. Có thể có nhiều lộ trình ngắn nhất, bạn chỉ cần đưa ra một trong số đó.
Dữ liệu vào
- Dòng đầu tiên gồm một số nguyên T (1 \leq T \leq 100) là số lượng bộ dữ liệu.
Với mỗi bộ dữ liệu:
- Dòng thứ 1 gồm hai số nguyên N và K (1 \leq K \leq N \leq 1000).
- Dòng thứ 2 gồm N −1 số nguyên p_i (1 \leq p_i \leq i), mô tả cạnh nối giữa p_i và i + 1.
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Dòng thứ 1 gồm một số nguyên L là độ dài của lộ trình (số cạnh đi qua).
- Dòng thứ 2 gồm L + 1 số nguyên x_i, là các điểm nằm trên lộ trình theo thứ tự đi qua.
Ví dụ
| Dữ liệu vào Sao chép |
3 6 2 1 1 2 2 3 6 6 1 1 2 2 3 6 4 1 2 3 4 5 |
| Dữ liệu ra Sao chép |
1 1 2 8 1 3 6 3 1 2 5 2 4 3 1 2 3 4 |
Gợi ý/Hướng dẫn
Hình minh họa cho cả ba bộ dữ liệu trong ví dụ:
