QTREE3 - Truy vấn trên cây

Giới hạn
  • Thời gian: 2.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một cây (đồ thị vô hướng phi chu trình) có N nút. Các nút của cây được đánh số từ 1 đến N. Ban đầu, mỗi nút đều có màu trắng.

Bạn phải thực hiện các thao tác có dạng sau:

  • 0 i : đổi màu nút thứ i (từ đen thành trắng, hoặc từ trắng thành đen)
  • 1 v : tìm chỉ số của nút đen đầu tiên trên đường đi từ nút 1 đến nút v. Nếu không tồn tại, hãy trả về -1.

Dữ liệu

  • Dòng thứ nhất gồm hai số nguyên N và Q .
  • N-1 dòng sau, mỗi dòng gồm hai số nguyên a b mô tả một cạnh nối giữa nút a và nút b .
  • Q dòng sau chứa các thao tác dạng "0 i" hoặc "1 v" (1 ≤ i, v ≤ N).

Kết quả

Với mỗi thao tác dạng " 1 v ", in ra một số nguyên là kết quả.

Ví dụ

Dữ liệu
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9 

Kết quả
-1
8
-1
2
-1

Giới hạn

Có 12 test:

  • Trong 1/3 số test, N=5000, Q=400000.
  • Trong 1/3 số test tiếp theo, N=10000, Q=300000.
  • Trong 1/3 số test tiếp theo, N=100000, Q=100000.

  • Người up: john_jones
  • Nguồn bài: VNOI Marathon '08 - Round 6/DivAProblem Setter: Blue Mary