Số Truy Vấn Tối Thiểu Tìm Đỉnh Trên Cây
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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ề
FOUNDvà 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$
Community Discussion