Cho T là một cây gồm N nút. Tổ tiên chung
gần nhất (LCA) của hai nút u và v được định nghĩa là nút thấp nhất trong T mà
có cả u và v làm con cháu. Nhiệm vụ của bạn trong bài này là tìm LCA của 2 nút
bất kỳ trong T.
Dữ liệu vào: Từ tệp văn bản LCA.INP
+ Dòng đầu tiên là số lượng TestCase. Mỗi
TestCase bắt đầu là một số nguyên N là số lượng nút trong cây
(1<=N<=1000), các nút được đánh số từ 1 đến N. N dòng tiếp theo, dòng thứ
i bắt đầu là M cho biết số lượng các nút con của nút thứ i (0<=M<=999).
Dòng tiếp theo là một số nguyên Q cho biết
số lượng câu hỏi cần trả lời. Tiếp theo là Q (1<=Q<=1000) dòng mỗi dòng
ghi 2 số nguyên u và v và yêu cầu tìm LCA của 2 nút u và v trong cây T.
Dữ liệu vào luôn có duy nhất 1 nút là nút
gốc của cây T và không có chu trình.
Dữ liệu ra: Ghi vào tệp văn bản LCA.OUT
Với mỗi TestCase ghi Q+1 dòng
+ Dòng đầu tiên ghi “Case C:” trong đó C
là thứ tự của Testcase bắt đầu từ 1
+ Q dòng tiếp theo mỗi dòng ghi LCA của u
và v tương ứng trong Input
Ví dụ:
LCA.INP
|
LCA.OUT
|
1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7
|
Case 1:
3
1
|
Không có nhận xét nào:
Đăng nhận xét