Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HBTLCA - dynamic LCA

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/hbtlca


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≤105).

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≤105).

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


Được gửi lên bởi:Thương
Ngày:2014-11-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Sưu tầm

hide comments
2021-05-27 18:00:52
Tham khảo: https://vnspoj.github.io/problems/HBTLCA
2020-06-30 11:59:56
tham khảo code AC ở đây: https://ideone.com/uVAIb8
2019-10-22 18:22:49
Á họ cài LCA mà TLE là sao T_T
2019-09-23 14:45:35
dăm ba cái lca :v
duonght_pro_xinhgainhathemattroi_:)
2017-11-28 14:49:21
Cảm ơn bạn bên dưới. Nếu bạn ko nhắc chắc mình làm đến sáng mai
2017-11-28 14:14:21
Chú ý làm multitest, ko để ý nộp WA chục lần
2017-11-28 10:02:11
ừ thì Điện cũng thông minh đấy
2017-11-28 10:01:45
như mấy thằng ngu í
2017-11-13 09:44:03
nhật hào sạch
2017-08-17 05:05:42
mất 1 đấm vì quên reset mảng sau mổi test.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.