dynamic LCA

View as PDF

Submit solution


Points: 0.38 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Sưu tầm
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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:

  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 \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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.