Tìm nút cha của một nút
Khi đã gốc hóa cây, biết nút cha của mỗi nút là đủ để làm rất nhiều việc: leo lên tìm tổ
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
Khi đã gốc hóa cây, biết nút cha của mỗi nút là đủ để làm rất nhiều việc: leo lên tìm tổ tiên, tính tổng trên đường đi, hay kiểm tra quan hệ trên cây. Bài này luyện đúng bước đầu tiên đó.
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 thêm một nút t (t != 1). Hãy in ra nhãn nút cha của t, tức nút kề duy nhất của t nằm gần gốc hơn một cạnh. Vì t != 1 nên nút cha luôn tồn tại.
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 một số nguyên, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: số nguyên n (2 <= 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: số nguyên t (2 <= t <= n).
Output
Một số nguyên duy nhất: nhãn nút cha của 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; nhãn nút cha không nhất
thiết nhỏ hơn nhãn nút con.
- Nhãn các nút không theo thứ tự duyệt, nên không thể suy ra cha từ giá trị 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
4
Output
2
Ví dụ 2
Input
6
1 2
2 3
2 4
4 5
4 6
5
Output
4
Giải thích
Dữ liệu vào:
Gốc là 1, các con của nó là 2 và 3; nút 2 có con 4. Vậy nút cha của 4 là 2, kết quả in ra là 2.
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.
