dynamic LCA
Xem dạng PDF
Gửi bài giải
Điểm:
0,38 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
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 đồ thị cây có ~N~ đỉnh ~N-1~ cạnh, có gốc là đỉnh ~1~. và ~M~ truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:
- ~root~: Chọn ~root~ làm gốc của cây
- ~u~ ~v~: Yêu cầu tìm cha chung gần nhất của hai đỉnh ~u~ và ~v~.
Hãy lập trình và đưa ra câu trả lời ứng với các truy vấn loại ~2~.
Input
Gồm nhiều bộ test:
- Dòng ~1~: Số nguyên ~N~, số đỉnh của cây ~(1 \leq N \leq 10^{5})~.
- ~N-1~ dòng tiếp theo: Mỗi dòng gồm hai số nguyên ~u~ và ~v~ là hai đỉnh của đồ thị.
- Dòng tiếp theo: Số nguyên ~M~, số truy vấn ~(1 \leq M \leq 10^{5})~.
- ~M~ dòng tiếp theo, mỗi dòng thuộc một trong hai loại truy vấn đã cho: "! ~root~" ứng với truy vấn loại ~1~ và "? ~u~ ~v~" ứng với truy vấn loại ~2~.
- Kết thúc bộ test là số ~0~.
Output
Đưa ra các câu trả lời ứng với các bộ, mỗi câu trả lời in ra trên một dòng.
Sample Input
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
0
Sample Output
2
1
3
6
Bình luận
mọi người cho mình hỏi là tại sao biến root khai báo toàn cục thì lại WA còn khai báo trong hàm main thì lại AC vậy nhỉ? thanks
bạn đã đặt lại root sau mỗi test về 1 chưa