Đèn Hiệu Gần Nhất

Buổi 46 — Centroid Decomposition
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

Đề 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 v hoặc 2 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$.
Draft saved