Elearning CodePath – CTP Online Judge

Tổ tiên chung gần gốc nhất

LCA_ROOT

🟢 Easy #Tree #LCA

### 📝 Bài toán
Cho một cây gồm n đỉnh, đỉnh 1 là gốc. Có q truy vấn, mỗi truy vấn cung cấp một tập hợp gồm k đỉnh: u1, u2, ..., uk. Nhiệm vụ của bạn là chọn ra hai đỉnh u_i và u_j từ tập hợp này sao cho Tổ tiên chung gần nhất (LCA) của chúng nằm gần gốc nhất (tức là có độ sâu nhỏ nhất). Nếu có nhiều cặp đỉnh thỏa mãn, hãy in ra bất kỳ cặp nào.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file LCA_ROOT.INP:
- Dòng đầu tiên gồm hai số nguyên n và q (1 <= n, q <= 10^5).
- n - 1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả một cạnh nối giữa u và v.
- q dòng tiếp theo, mỗi dòng mô tả một truy vấn:
    - Số nguyên đầu tiên k (2 <= k <= n) là số lượng đỉnh trong tập.
    - k số nguyên tiếp theo là các đỉnh của tập hợp đó.
- Tổng các giá trị k trong tất cả các truy vấn không vượt quá 2 * 10^5.

### 📤 Định dạng Đầu ra
Với mỗi truy vấn, in ra hai số nguyên là tên của hai đỉnh có LCA gần gốc nhất.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 8 7 | 2 6 |
| 1 2 | 2 3 |
| 2 3 | 2 6 |
| 1 4 | 3 4 |
| 2 5 | 2 6 |
| 4 6 | 1 8 |
| 5 7 | 2 5 |
| 7 8 | |
| 5 4 5 2 2 6 | |
| 3 2 2 3 | |
| 6 6 2 5 3 2 2 | |
| 3 4 3 3 | |
| 5 6 3 8 7 2 | |
| 4 2 1 8 5 | |
| 2 5 2 | |

### 🏷 Subtasks
- Subtask 1 (30%): n, q <= 1000; k <= 100.
- Subtask 2 (70%): n, q <= 10^5; Tổng k <= 2 * 10^5.

✅ Đã AC: 0 / 4 submissions