Cấp dưới

Đề bài

Mô tả

Trong một công ty có n nhân viên, mỗi nhân viên có một mã số duy nhất từ 1 đến n. Một trong số họ là sếp tổng, với mã số là s. 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ứ i báo cáo con số ai. 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 s là sếp tổng).

Dữ liệu vào

  • Dòng 1: hai số nguyên dương ns (1n2·105, 1sn).
  • Dòng 2: n số nguyên a1,a2,,an (0ain1).

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

  • 1n2·105
  • 1sn
  • 0ain1

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 3, đã báo cáo đúng a3=0. Có thể chọn cấu trúc trong đó nhân viên 4 (báo 4) và một nhân viên khác đã báo sai, tổng cộng 2 người sai.
3 2
2 0 2
1 Có thể giả định chỉ nhân viên 1 báo sai: nếu cấp trên trực tiếp của nhân viên 1 là nhân viên 2, cấp trên trực tiếp của nhân viên 3 là nhân viên 1, và nhân viên 2 là sếp tổng, thì các báo cáo a2=0a3=2 đều đúng.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0