Kiểm tra một nút có phải tổ tiên của nút khác
Quan hệ "tổ tiên - hậu duệ" là câu hỏi xuất hiện liên tục khi làm việc với cây: kiểm tra
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Quan hệ "tổ tiên - hậu duệ" là câu hỏi xuất hiện liên tục khi làm việc với cây: kiểm tra phân cấp thư mục, kiểm tra vùng chứa nhau, hay dựng cây LCA. Ở dạng nhỏ nhất, bài toán chỉ là: nút u có nằm trên đường đi từ gốc tới nút v hay không?
Yêu cầu
Cho một cây gồm n nút đánh số từ 1 đến n và n - 1 cạnh. Quy ước: nút 1 là gốc của cây, mỗi cạnh có thể được ghi theo chiều bất kỳ.
Cho hai nút u và v. Nút u được gọi là tổ tiên của nút v nếu u nằm trên đường đi duy nhất từ gốc 1 tới v và u khác v. Hãy in ra YES nếu u là tổ tiên của v, ngược lại in NO. Lưu ý u = v không tính là tổ tiên, và gốc 1 là tổ tiên của mọi nút khác 1.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng YES hoặc NO viết hoa, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: số nguyên n (1 <= n <= 10).
- n - 1 dòng tiếp theo: mỗi dòng hai số nguyên u v là một cạnh của cây.
- Dòng cuối cùng: hai số nguyên u v (1 <= u, v <= n) là câu hỏi cần trả lời.
- Khi n = 1 thì không có dòng cạnh nào và câu hỏi luôn là 1 1.
Output
In ra YES hoặc NO trên một dòng duy nhất.
Ràng buộc
- Dữ liệu luôn là một cây hợp lệ: liên thông, đúng n - 1 cạnh, không có cạnh lặp.
- Thứ tự các dòng cạnh là tùy ý, cạnh có thể ghi con trước cha.
- u = v phải cho kết quả NO (quan hệ tổ tiên ở đây là quan hệ nghiêm ngặt).
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
4
1 2
1 3
2 4
1 4
Output
YES
Ví dụ 2
Input
4
1 2
1 3
2 4
3 4
Output
NO
Giải thích
Dữ liệu vào:
Đường đi từ gốc 1 tới nút 4 là 1 -> 2 -> 4, nên nút 1 nằm trên đường đi đó và khác 4. Kết quả in ra là YES.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
