Đèn Hiệu Gần Nhất
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Ban đầu, chỉ có đỉnh $1$ được bật đèn hiệu màu đỏ, các đỉnh còn lại đều màu xanh.
Bạn cần xử lý $Q$ truy vấn thuộc một trong hai loại sau:
1 v: Bật đèn hiệu màu đỏ tại đỉnh $v$ (nếu $v$ đã màu đỏ thì giữ nguyên).2 v: Tìm khoảng cách ngắn nhất (tính bằng số cạnh) từ đỉnh $v$ đến một đỉnh màu đỏ bất kỳ.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ biểu thị một cạnh của cây.
- $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn có dạng
1 vhoặc2 v($1 \le v \le N$).
Dữ liệu ra
- Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.
Ví dụ
Dữ liệu vào
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
Dữ liệu ra
0
3
2
Giới hạn
- $1 \le N, Q \le 10^5$.
Community Discussion