HBTLCA - dynamic LCA
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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:
1 root: Chọn root làm gốc của cây
2 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≤N≤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≤M≤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.
Example
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
Output:2
1
3
6
- Người up: only_love97
- Nguồn bài: Sưu tầm