Cấp dưới
Đề bài
Mô tả
Trong một công ty có nhân viên, mỗi nhân viên có một mã số duy nhất từ đến . Một trong số họ là sếp tổng, với mã số là . Mỗi nhân viên khác sếp tổng có đúng một cấp trên trực tiếp.
Cấp trên (không nhất thiết trực tiếp) của một nhân viên là: cấp trên trực tiếp của họ, cấp trên trực tiếp của cấp trên trực tiếp đó, và cứ thế. Sếp tổng là cấp trên của tất cả các nhân viên còn lại.
Người ta yêu cầu từng nhân viên báo cáo số lượng cấp trên (tính cả trực tiếp lẫn gián tiếp) của mình. Nhân viên thứ báo cáo con số . Một số người vội vàng và có thể đã báo cáo sai.
Hãy tìm số lượng nhân viên ít nhất có thể đã báo cáo sai, biết rằng các con số còn lại phải tương ứng với một cấu trúc công ty hợp lệ nào đó (với là sếp tổng).
Dữ liệu vào
- Dòng 1: hai số nguyên dương và (, ).
- Dòng 2: số nguyên ().
Dữ liệu ra
- Một số nguyên duy nhất — số nhân viên ít nhất có thể đã báo cáo sai.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 1 0 0 4 1 |
2 | Sếp tổng là nhân viên , đã báo cáo đúng . Có thể chọn cấu trúc trong đó nhân viên (báo ) và một nhân viên khác đã báo sai, tổng cộng người sai. |
| 3 2 2 0 2 |
1 | Có thể giả định chỉ nhân viên báo sai: nếu cấp trên trực tiếp của nhân viên là nhân viên , cấp trên trực tiếp của nhân viên là nhân viên , và nhân viên là sếp tổng, thì các báo cáo và đều đúng. |
Bình luận