Trang trí cây
Đề bài
Mô tả
Đây là một bài toán tương tác.
Thắng và Trang định trang trí nhà bằng một cây thông Noel. Họ muốn cây là một đồ thị liên thông gồm đỉnh đánh số từ đến và cạnh.
Như mọi năm, Trang rất háo hức đón Giáng sinh. Đầu tiên, Trang tạo một cây gồm đỉnh đánh số từ đến với cạnh.
Sau khi Trang làm xong, Thắng thêm đỉnh còn lại và cạnh mà không cho Trang xem cây cuối cùng. Đảm bảo cây cuối cùng liên thông.
Thắng đố Trang tìm đường kính của cây, tức là độ dài lớn nhất của một đường đi đơn giữa hai đỉnh của cây (độ dài đường đi là số cạnh trên đường đi).
Làm quà Giáng sinh, Thắng cho phép Trang hỏi không quá câu hỏi thuộc các loại sau:
- distance u v: Thắng cho biết khoảng cách giữa hai đỉnh và trên cây;
- subtree u v: xét cây với gốc là đỉnh , Thắng cho biết khoảng cách lớn nhất từ đến một đỉnh thuộc cây con gốc .
Dữ liệu vào
Chương trình của bạn đóng vai Trang, chương trình chấm đóng vai Thắng. Quá trình tương tác như sau:
- Đầu tiên, chương trình của bạn đọc hai số nguyên và .
- Tiếp theo, in ra dòng, mỗi dòng gồm hai số nguyên , () thể hiện một cạnh của cây đỉnh mà Trang tạo. Các cạnh này phải tạo thành một cây trên các đỉnh .
- Sau đó, chương trình chấm thêm các đỉnh cùng cạnh (cây cuối cùng đã được xác định trước, chỉ phụ thuộc vào cây của bạn qua số hiệu các đỉnh), và bạn được hỏi không quá câu hỏi:
- in ra distance u v (, ) rồi đọc khoảng cách giữa và ;
- in ra subtree u v (, ) rồi đọc khoảng cách lớn nhất từ đến một đỉnh thuộc cây con gốc khi cây có gốc .
- Cuối cùng, in ra dấu chấm than và một số nguyên là đường kính của cây (ví dụ ! 3), rồi kết thúc chương trình.
Sau khi in mỗi dòng, đừng quên in ký tự xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() (hoặc endl) trong C++, sys.stdout.flush() trong Python.
Dữ liệu ra
Các cạnh, các câu hỏi và câu trả lời cuối cùng được in theo đúng định dạng mô tả ở trên.
Ràng buộc
- , .
- Không quá câu hỏi.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 1 2 3 3 1 2 2 1 1 2 |
1 2 distance 1 2 distance 1 3 distance 1 4 distance 1 5 distance 2 3 distance 2 4 distance 2 5 distance 3 4 distance 3 5 distance 4 5 ! 3 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Trang tạo cây gồm cạnh ; Thắng thêm các cạnh , , . Ở đây chương trình hỏi khoảng cách của mọi cặp đỉnh; lớn nhất là (giữa và ). Đề gốc minh họa cùng cây này bằng các câu hỏi distance 1 4 (trả lời ), distance 1 5 (trả lời ) và subtree 3 2 (trả lời : gốc , cây con gốc gồm đỉnh và ), rồi in !3. |
| 1 3 1 2 1 |
distance 1 2 distance 1 3 distance 2 3 ! 2 |
Ví dụ bổ sung: nên Trang không in cạnh nào. Thắng thêm các cạnh và , đường kính là . |
Bình luận