TREECST - Tree Construction
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.
Xây dựng cây
Cho một cây có N đỉnh. Tìm cách xóa đi một cạnh thuộc cây và thêm vào một cạnh mới, sao cho sau đó, độ dài đường đi dài nhất trên cây là nhỏ nhất có thể. Độ dài của một đường đi được tính bằng số cạnh thuộc đường đi đó.
Dữ liệu
Dòng đầu tiên chứa số N (1 ≤ N ≤ 300 000).
N-1 dòng sau, mỗi dòng chứa 2 số nguyên mô tả một cạnh của cây.
Kết quả
- Dòng đầu tiên in ra độ dài nhỏ nhất tìm được.
- Dòng thứ hai ghi 2 số nguyên cho biết cạnh cần xóa.
- Dòng thứ ba ghi 2 số nguyên cho biết cạnh cần thêm vào.
Nếu có nhiều lời giải, chỉ cần in ra một lời giải bất kỳ.Ví dụ
Dữ liệu 4 1 2 2 3 3 4 Kết quả 2 3 4 4 2 Dữ liệu 7 1 3 2 3 2 7 4 3 7 5 3 6 Kết quả 3 2 3 7 3
- Người up: paulmcvn
- Nguồn bài: COCI 2008-2009, #1