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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.



  • 1
    PaDi  commented on May 16, 2024, 6:02 p.m.

    Thuật ko cần dùng segtri: Sử dụng chặt nhị phân và cây BIT. Với mỗi truy vấn 0 i thì update giá trị tại i += 1 nếu i trắng. Còn nếu i đen thì giá trị tại i -= 1. Với mỗi truy vấn 1 v, khi nhảy chuỗi từ v lên gốc là 1. Với mỗi chuỗi L,R ta sẽ tìm chỉ số x bé nhất trong đoạn L,R mà tồn tại điểm màu đen từ L đến x. Điều đó tương đương get(x) - get(L-1) >= 1 với get(u) là tổng số màu đen cho đến u. Ta sử dụng chặt nhị phân để tìm x. Sau khi tìm được x. Lấy min X của mọi x tìm được. Trả về kết quả là tour[X]. Bài toán hoàn tất.