VM 08 Bài 15 - Truy vấn trên cây
Xem dạng PDF
Gửi bài giải
Điểm:
0,74 (OI)
Giới hạn thời gian:
3.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
Mình có một thuật khá hay cho bài này
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.