Đếm số lá của cây có gốc
Một cây gia phả thường được ghi bằng "cha của mỗi người". Trong cây có gốc, lá là những
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
Một cây gia phả thường được ghi bằng "cha của mỗi người". Trong cây có gốc, lá là những đỉnh không có con nào. Đếm lá cho biết cây phân nhánh tới đâu và có bao nhiêu "đầu mút" không dẫn tới ai nữa.
Yêu cầu
Cây có n đỉnh đánh số 1..n và gốc là đỉnh 1. Dữ liệu cho mảng cha: p[1] = 0 vì gốc không có cha, còn với i từ 2 tới n thì p[i] là cha của đỉnh i. Hãy đếm số đỉnh không có con nào (gọi là lá). Đỉnh gốc cũng được tính là lá nếu nó không có con nào, chẳng hạn trường hợp n = 1.
Quy ước nộp bài
Nộp tệp 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 gì khác. Chỉ dùng thư viện chuẩn C++17.
Input
- Dòng đầu tiên: một số nguyên n (1 <= n <= 8).
- Dòng thứ hai: n số nguyên p[1], p[2], ..., p[n] cách nhau bởi dấu cách, trong đó
p[1] = 0 và với i >= 2 thì 1 <= p[i] <= n, p[i] != i. Dữ liệu luôn mô tả một cây hợp lệ.
Output
In ra stdout một số nguyên duy nhất: số đỉnh không có con nào.
Ràng buộc
- Dữ liệu vào luôn là một cây có gốc là đỉnh 1 và không có cạnh thừa.
- Số lá tối thiểu là 1 (cây chỉ có gốc).
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
5
0 1 1 2 2
Output
3
Ví dụ 2
Input
3
0 1 1
Output
2
Giải thích
Dữ liệu vào:
Đỉnh 1 có hai con là 2 và 3; đỉnh 2 có hai con là 4 và 5; các đỉnh 3, 4, 5 không có con nào. Vậy có 3 lá và kết quả là:
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.
