Link bài tập gốc (tiếng Anh)
http://www.vnoi.info/problems/show/QTREE5/
Đề bài (tiếng Việt)
Cho 1 cây với N đỉnh được đánh số từ 1 đến N. Ta định nghĩa dist(a, b) là số lượng cạnh trên đường đi từ đỉnh a đến đỉnh b.
Mỗi nút có một màu, đen hoặc trắng. Khởi tạo mọi nút là màu đen.
Bạn phải thực hiện các truy vấn sau:
- 0 i : Thay đổi màu của nút i (đen thành trắng hoặc trắng thành đen)
- 1 v : Đưa ra giá trị nhỏ nhất của dist(u, v), với nút u là một nút trắng(u có thể bằng v). Nếu nút v là nút trắng, kết quả là 0.
Input
- Dòng thứ nhất chứa 1 số nguyên dương N (N <= 100000)
- N-1 dòng tiếp theo, dòng thứ i có 2 số nguyên dương a, b biểu diễn một cạnh giữa a và b
- Dòng tiếp theo là số nguyên dương Q là số truy vấn (Q <= 100000)
- Q dòng tiếp theo, mỗi dòng có dạng “0 i” hoặc ”1 v”
Output
Với mỗi truy vấn dạng ”1 v”, in ra 1 số nguyên dương biễu diễn kết quả. Nếu không có nút trắng nào trên cây, in ra -1