Subtask 1&4:

Ta làm thao tác sau ~\frac{N - 1}{2}~ lần

• Gọi tập C là tập candidates còn lại (~0~-indexed), sz là độ lớn của tập

• Ta chặt nhị phân trên tập candidates còn lại để tìm cạnh có độ dài có độ dài bé nhất

• Ta CNP vị trí ~l~ lớn nhất sao cho trong ~C[l], C[l + 1], ..., C[sz - 1]~ tồn tại cạnh bé nhất.

• Ta tiếp tục CNP vị trí ~r~ nhỏ nhất sao cho trong ~C[l], C[l + 1], ..., C[r]~ tồn tại cạnh bé nhất.

• Ta xác định được ~C[l], C[r]~ là 2 đầu mút của cạnh bé nhất trong các candidates còn lại. Ta xóa ~2~ đỉnh này ra khỏi tập candidates.

Chứng minh đúng: Nếu đỉnh còn lại bị bắn bởi một trong các đỉnh khác, thì đáng lẽ chúng phải tạo thành cạnh bé nhất ở một trong các bước trên.

Nếu các bạn tính số query ra thì thuật này sẽ ăn được ~42~ điểm. Để full sub ~4~, ta có thể làm như sau:

• Giả sử cạnh bé nhất từ lần tìm trước có độ dài là ~x~, ta sẽ thử ~x + 2^{10}, x + 2 * 2^{10}, ...~ đến khi nào có ít nhất một cạnh thỏa mãn.

• Ta chỉ cần chặt nhị phân trong một khoảng ~2^{10}~ thay vì ~3 * 10^6~. Ngoài ra, việc tăng trên chỉ xuất hiện ~\frac{3 * 10^6}{2^{10}} + n~ lần (bạn đọc có thể tự chứng minh).

Subtask 2&3 (tác giả chưa chứng minh được vì sao ăn hết)

• Giả sử chúng ta đã tìm được một số cạnh, và chúng ta muốn tìm cạnh mới. Đồ thị hiện tại có dạng forest.

• Với mỗi cây, ta tô bipartite (random root là ~0~ hoặc ~1~), và hỏi tập chứa các đỉnh được đánh số ~0~ cũng như ~1~ để tìm xem có cạnh không. Ta dễ dàng chứng minh xác suất tìm được là ~1 - \frac{1}{2^x}~ với ~x~ là số cạnh còn lại.

  => Gần như chắc chắn là bước nào chúng ta cũng tìm được cạnh như vậy trừ một số bước cuối khi ~x~ bé.

• Ta CNP độ dài cạnh và 2 đỉnh như subtask 1&4

Với cách trên, ta tìm hết ~n - 1~ cạnh rồi for trâu để tìm đỉnh (nếu có).

Tác giả không chắc vì sao số thao tác lại ~\leq 41000~, bạn đọc có thể chứng minh.