Có \(N\) địa điểm và một cây giao thông bí mật gồm \(N-1\) cạnh. Với mỗi đỉnh bắt đầu \(i\), ban giám khảo cố định một thứ tự duyệt DFS của toàn bộ cây, bắt đầu tại \(i\). Thứ tự xét các đỉnh kề có thể khác giữa các lần DFS.

Hình 1: Một lượt DFS bắt đầu ở đỉnh \(4\); các mũi tên được đánh số theo thứ tự di chuyển.

Bạn được hỏi phần tử thứ \(j\) trong thứ tự DFS bắt đầu tại \(i\). Hãy khôi phục chính xác cây bí mật. Cây và mọi thứ tự DFS được cố định trước khi chương trình chạy.

Giao diện thư viện

Submission C++ phải include reconstruct.h và cài đặt:

std::vector<std::pair<int, int>> find_tree(int N);

Grader cung cấp:

int guess(int i, int j);

guess(i,j) trả về địa điểm thứ \(j\) trong thứ tự DFS bắt đầu tại \(i\); đặc biệt guess(i,0)=i. Mọi chỉ số phải thuộc \([0,N-1]\). find_tree phải trả đúng \(N-1\) cạnh, với hai đầu mút được đánh số từ \(0\) đến \(N-1\); thứ tự cạnh và thứ tự hai đầu mút không quan trọng. Hàm có thể được gọi \(T\) lần trong một test.

Đây là bài giao tiếp. Submission chạy trong một tiến trình riêng và chỉ được trao đổi với manager qua các hàm trên.

Dữ liệu vào

Submission không đọc standard input. Manager đọc các cây và thứ tự DFS ẩn từ bộ test.

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả từ find_tree.

Ràng buộc

• \(2\le N\le2^{16}+1\).
• Nếu \(N_{\max}\le9\) thì \(1\le T\le100\).
• Nếu \(N_{\max}\le2^{10}+1\) thì \(1\le T\le10\).
• Nếu \(N_{\max}\le2^{16}+1\) thì \(1\le T\le3\).
• guess chạy trong \(O(1)\) ở các phân nhóm 1--6 và \(O(\log N)\) ở phân nhóm 7.
• System grader có thể dùng tối đa \(280\) MiB, được tính trong giới hạn bộ nhớ.

Phân nhóm

1. \(11\) điểm: \(N\le9\).
2. \(6\) điểm: \(N\le100\) và bậc mỗi đỉnh không quá \(2\).
3. \(13\) điểm: \(N\le100\); mỗi DFS luôn ưu tiên đi xa đỉnh \(0\), và nếu có nhiều lựa chọn thì chọn tùy ý.
4. \(11\) điểm: \(N\le100\) và mọi đỉnh khác \(0\) có bậc không quá \(2\).
5. \(10\) điểm: \(N\le100\).
6. \(31\) điểm: \(N\le2^{10}+1\).
7. \(18\) điểm: \(N\le2^{16}+1\).

Ở phân nhóm 6 và 7, gọi \(Q_{\max}\) là số truy vấn lớn nhất trong một lần gọi. Điểm theo tỉ lệ \(S\): \(S=1\) nếu \(Q_{\max}\le L_1\); \(S=0.4+0.6(L_2-Q_{\max})/(L_2-L_1)\) nếu \(L_1<Q_{\max}\le L_2\); \(S=0.2+0.2(3L_2-Q_{\max})/(2L_2)\) nếu \(L_2<Q_{\max}\le3L_2\); và \(S=0.2\) nếu \(Q_{\max}>3L_2\). Phân nhóm 6 dùng \((L_1,L_2)=(3075,9225)\); phân nhóm 7 dùng \((196611,983055)\). Điểm của phân nhóm là tỉ lệ nhỏ nhất trên mọi test.

Hình 2: Điểm của phân nhóm 6 theo số truy vấn lớn nhất.

Hình 3: Điểm của phân nhóm 7 theo số truy vấn lớn nhất.

Ví dụ

Hình 4: Cây giao thông bí mật của ví dụ.

Với một cây có \(6\) đỉnh và thứ tự DFS từ đỉnh \(0\) là [0, 1, 2, 4, 3, 5], các lời gọi guess(0,j) lần lượt trả các phần tử trên. Một kết quả hợp lệ có thể gồm các cạnh (0,1), (0,2), (4,0), (5,4), (3,4).

Nguồn

EJOI 2026 - Ngày 1, Reconstruct.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).