Số Truy Vấn Tối Thiểu Tìm Đỉnh Trên Cây

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

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Có một đỉnh bí mật $X$ nằm trên cây. Trong trò chơi tương tác, ở mỗi lượt bạn được chọn một đỉnh $u$ trên cây để hỏi:

  • Nếu $u = X$, máy chấm trả về FOUND và trò chơi kết thúc.
  • Nếu $u \ne X$, máy chấm chỉ ra đỉnh kề $v$ của $u$ nằm trên đường đi từ $u$ đến $X$ (giúp thu hẹp vùng tìm kiếm về thành phần liên thông chứa $v$ sau khi loại bỏ $u$).

Lưu ý rằng bạn không bắt buộc phải chọn trọng tâm (đôi khi chọn đỉnh khác giúp giảm số lượt tối đa trong trường hợp xấu nhất). Hãy tìm số lượt hỏi ít nhất trong trường hợp xấu nhất để chắc chắn tìm ra $X$ (tính cả lượt hỏi cuối cùng nhận FOUND) với chiến lược thích nghi tối ưu.

Dữ liệu vào
  • Dòng đầu ghi số nguyên $N$ ($1 \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
  • Một số nguyên duy nhất là số lượt hỏi tối thiểu trong trường hợp xấu nhất.
Ví dụ
Input Output
7
1 2
2 3
3 4
4 5
5 6
6 7
3
Giới hạn
  • $1 \le N \le 10^5$
Draft saved