Cowboy Coder

To code like a Cowboy!

[SPOJ] QTREE3 - Query on a tree again!

Link đề bài : http://vnoi.info/problems/show/QTREE3/

Đề bài:

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.

Input :

  • Dòng thứ nhất gồm hai số nguyên NQ.
  • 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).

Output :

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

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.

Solution:

http://viahold.com/1mJA

Code:

http://viahold.com/1mJm