Truy Tìm Đỉnh Ẩn Bằng Trọng Tâm Cây

Buổi 63 — Interactive & Constructive Trees
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ cây và đỉnh bí mật được cho trước).

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$ và một đỉnh bí mật $X$. Trong trò chơi tương tác, bạn được phép hỏi một đỉnh $u$ bất kỳ:

  • Nếu $u = X$, máy chấm trả về FOUND và trò chơi kết thúc.
  • Ngược lại, máy chấm cho biết đỉnh kề $v$ của $u$ nằm trên đường đi từ $u$ đến $X$ (khi đó vùng ứng viên thu hẹp về thành phần liên thông chứa $v$ sau khi xóa $u$).

Chiến lược tối ưu luôn chọn trọng tâm (centroid) của thành phần liên thông hiện tại để hỏi (nếu có hai trọng tâm, chọn đỉnh có chỉ số nhỏ hơn). Hãy mô phỏng chiến lược này và in ra thứ tự các đỉnh trọng tâm đã hỏi cho đến khi tìm được $X$.

Dữ liệu vào
  • Dòng đầu ghi hai số nguyên $N$ và $X$ ($1 \le X \le N \le 10^5$).
  • $N - 1$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $u, v$ mô tả cạnh của cây.
Dữ liệu ra
  • Dòng đầu ghi số nguyên $K$ là số lần hỏi.
  • Dòng thứ hai ghi $K$ số nguyên là các đỉnh đã hỏi theo thứ tự.
Ví dụ
Input Output
5 4
1 2
2 3
3 4
4 5
2
3 4
Giới hạn
  • $1 \le X \le N \le 10^5$
Draft saved