Xenia and Tree
Xem dạng PDF
Xenia — một lập trình viên, có một cái cây gồm ~n~ đỉnh. Các đỉnh được đánh số từ ~1~ tới ~n~ và có màu xanh hoặc đỏ. Ban đầu, đỉnh ~1~ được tô màu đỏ, trong khi các đỉnh còn lại được tô màu xanh.
Khoảng cách giữa hai đỉnh ~u~ và ~v~ được định nghĩa là số cạnh trên đường đi ngắn nhất từ ~u~ tới ~v~.
Xenia có các truy vấn thuộc ~1~ trong ~2~ loại sau:
~1\ i~: tô đỉnh ~i~ từ màu xanh thành màu đỏ.
~2\ i~: In khoảng cách ngắn nhất từ đỉnh ~i~ tới một đỉnh đang có màu đỏ (nếu đỉnh ~i~ đang được tô màu đỏ thì đáp án sẽ là ~0~).
Vì Xenia không thể giải được bài toán trên nên bạn hãy giúp anh ấy giải bài toán này nhé!
Input
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~2 \leq n \leq 10^5~, ~1 \leq m \leq 10^5~), lần lượt là số đỉnh của cây và số truy vấn của bài toán.
Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa hai số nguyên dương ~a_i~ và ~b_i~ (~1 \leq a_i, b_i, \leq n~, ~a_i \neq b_i~) thể hiện một cạnh của cây.
Mỗi dòng trong số ~m~ dòng tiếp theo gồm 2 số có dạng ~1\ i~ hoặc ~2\ i~ (~1 \leq i \leq n~) thể hiện một truy vấn thuộc ~2~ loại truy vấn ở trên.
Dữ liệu đảm bảo lúc thực hiện truy vấn ~1~ thì đỉnh ~i~ đang có màu xanh.
Output
Với mỗi truy vấn thuộc loại ~2~ thì in ra câu trả lời cho truy vấn đó.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~20~ | ~n, q \leq 5000~ |
| ~2~ | ~30~ | Mọi truy vấn ~1~ diễn ra trước truy vấn ~2~ |
| ~3~ | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
3 3
1 2
2 3
2 3
1 2
2 3
Sample Output 1
2
1
Sample Input 2
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
Sample Output 2
0
3
2
Notes
Ở test ví dụ đầu tiên:
Trong truy vấn loại ~2~ đầu tiên, đỉnh màu đỏ gần với đỉnh ~3~ nhất là đỉnh ~1~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(3, 1) = 2~.
Trong truy vấn loại ~2~ tiếp theo, đỉnh màu đỏ gần với đỉnh ~3~ nhất là đỉnh ~2~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(3, 2) = 1~.
Ở test ví dụ thứ hai:
Trong truy vấn loại ~2~ đầu tiên, đỉnh ~1~ đã được tô màu đỏ nên khoảng cách của đỉnh này tới đỉnh màu đỏ gần nhất là ~d(1, 1) = 0~.
Trong truy vấn loại ~2~ tiếp theo, đỉnh màu đỏ gần với đỉnh ~5~ nhất là đỉnh ~1~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(5, 1) = 3~.
Trong truy vấn loại ~2~ cuối cùng, đỉnh màu đỏ gần với đỉnh ~5~ nhất là đỉnh ~2~ nên khoảng cách tới đỉnh màu đỏ gần nhất là ~d(5, 2) = 2~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
true story
ok ban
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.