TRIPHP - Chuyến đi ngắn nhất
Giới hạn- Thời gian: 3.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Làng của Buba là nơi nổi tiếng với nhiều danh lam thắng cảnh, thu hút hàng nghìn khách du lịch từ nhiều nơi trên thế giới. Làng có địa điểm du lịch (đánh số từ 1 đến ) và con đường độ dài 1 nối các cặp địa điểm. Hai địa điểm bất kì đều có thể đi đến nhau qua các con đường này.
Có khách du lịch tại địa điểm 1, những người khách được đánh số từ 1 tới . Người khách thứ nhất muốn thăm tất cả các địa điểm, người khách thứ hai muốn thăm tất cả các địa điểm chia hết cho 2, người khách thứ ba muốn thăm tất cả các địa điểm chia hết cho 3, … Cụ thể là người khách thứ muốn thăm tất cả các địa điểm chia hết cho .
Yêu cầu: Công ty du lịch muốn lập hành trình cho từng du khách bắt đầu từ địa điểm 1 đi thăm các địa điểm khác rồi quay trở về địa điểm 1 sao cho mỗi du khách được đi qua tất cả các địa điểm anh ta muốn thăm (hành trình có thể qua những địa điểm khác nữa). Bạn cần cho biết độ dài hành trình ngắn nhất của mỗi du khách thỏa mãn yêu cầu trên.
Ví dụ
Giải thích về hành trình vài du khách
Du khách 1 đi theo hành trình
Du khách 2 và 4 đi theo hành trình
Ít nhất 40% số điểm ứng với các test có N <= 100
Input
- Dòng 1: Chứa số nguyên dương N <= 10^5.
- N dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v cách nhau ít nhất một dấu cách mô tả một con đường nối địa điểm tới địa điểm .
Output
Ghi ra file văn bản dòng, dòng thứ ghi một số nguyên duy nhất là độ dài quãng đường ngắn nhất mà du khách thứ phải đi
Example
Input: 5 1 2 1 3 4 2 5 2 Output: 8 4 2 4 4
- Người up: voj