VM 08 Bài 15 - Truy vấn trên cây

View as PDF

Submit solution

Points: 0.74 (partial)
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 6/DivAProblem Setter: Blue Mary
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 ~N~ và ~Q~. ~(1 \le N, Q \le 10^5)~.
  • ~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~ ~(1 \le a, b \le N)~.
  • ~Q~ dòng sau chứa các thao tác dạng ~0 \, i~ hoặc ~1 \, v~ ~(1 \le i, v \le N)~.

Output

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

Sample Input

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

Sample Output

-1
8
-1
2
-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.