trang chủ / đề bài / icpc22_nat_d

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 n đỉnh đánh số từ 1 đến n và n−1 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 m đỉnh đánh số từ 1 đến m với m−1 cạnh.

Sau khi Trang làm xong, Thắng thêm n−m đỉnh còn lại và n−m 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á 666 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 u và v trên cây;
  • subtree u v: xét cây với gốc là đỉnh u, Thắng cho biết khoảng cách lớn nhất từ u đến một đỉnh thuộc cây con gốc v.

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 m và n.
  • Tiếp theo, in ra m−1 dòng, mỗi dòng gồm hai số nguyên u, v (1≤u,v≤m) thể hiện một cạnh của cây m đỉ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 1,2,…,m.
  • Sau đó, chương trình chấm thêm các đỉnh m+1,…,n cùng n−m 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á 666 câu hỏi:
    • in ra distance u v (1≤u,v≤n, u≠v) rồi đọc khoảng cách giữa u và v;
    • in ra subtree u v (1≤u,v≤n, u≠v) rồi đọc khoảng cách lớn nhất từ u đến một đỉnh thuộc cây con gốc v khi cây có gốc u.
  • 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

  • 1≤m≤5·104, m<n≤3m.
  • Không quá 666 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 1−2; Thắng thêm các cạnh 2−3, 3−4, 3−5. Ở đây chương trình hỏi khoảng cách của mọi cặp đỉnh; lớn nhất là 3 (giữa 1 và 4). Đề 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 3), distance 1 5 (trả lời 3) và subtree 3 2 (trả lời 2: gốc 3, cây con gốc 2 gồm đỉnh 2 và 1), rồi in !3.
1 3
1
2
1
distance 1 2
distance 1 3
distance 2 3
! 2
Ví dụ bổ sung: m=1 nên Trang không in cạnh nào. Thắng thêm các cạnh 1−2 và 2−3, đường kính là 2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0