trang chủ / đề bài / icpc24_mt_i

Giúp tôi với, sếp ơi

Đề bài

Mô tả

Bạn quản lý một nhóm gồm n nhân viên, mỗi người có một mã số riêng từ 1 đến n, mã số của bạn là 1. Mỗi nhân viên, trừ bạn, có đúng một cấp trên trực tiếp có mã số nhỏ hơn mã số của mình.

  • Nếu nhân viên i là cấp trên trực tiếp của nhân viên j thì i được coi là cấp trên của j.
  • Nếu nhân viên i là cấp trên của nhân viên j, và j là cấp trên của nhân viên k, thì i cũng được coi là cấp trên của k.

Mỗi nhân viên được giao đúng một công việc. Nhân viên có thể tự hoàn thành công việc của mình hoặc chuyển nó lên một trong các cấp trên của mình. Một nhân viên có thể đảm nhận nhiều công việc, nhưng càng nhận nhiều việc thì càng căng thẳng. Cụ thể, nhân viên i có hệ số căng thẳng fi; nếu nhân viên i đảm nhận m công việc thì mức căng thẳng của họ là fi×m.

Xét mọi cách phân chia có thể, hãy đếm số nhân viên có khả năng trở thành người căng thẳng nhất, tức là có mức căng thẳng cao nhất trong cả n nhân viên (nếu nhiều người cùng có mức cao nhất thì tất cả đều được coi là căng thẳng nhất).

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương n (2≤n≤106): số nhân viên.
  • Dòng thứ hai chứa n−1 số nguyên a2,a3,…,an, trong đó ai là cấp trên trực tiếp của nhân viên i (1≤ai<i).
  • Dòng thứ ba chứa n số nguyên f1,f2,…,fn (1≤fi≤1012): hệ số căng thẳng của các nhân viên.

Dữ liệu ra

In ra một số nguyên: số nhân viên có khả năng trở thành người căng thẳng nhất.

Ràng buộc

  • 2≤n≤106
  • 1≤ai<i
  • 1≤fi≤1012

Ví dụ

Input Output Giải thích
3
1 1
2 1 1
1 Nhân viên 1 luôn phải tự làm việc của mình nên có mức căng thẳng ít nhất 2, trong khi nhân viên 2 và 3 có mức tối đa là 1. Chỉ nhân viên 1 có thể căng thẳng nhất.
4
1 1 2
1 1 1 1
4 Nếu mỗi người tự làm việc của mình, mức căng thẳng của mọi người đều bằng 1: cả 4 người đều là người căng thẳng nhất.
5
1 1 3 3
2 1 1 1 4
3 Các nhân viên 1, 3, 5 có thể căng thẳng nhất. Chẳng hạn với nhân viên 3: nhân viên 1 tự làm việc của mình (mức 2), nhân viên 2 tự làm việc của mình (mức 1), nhân viên 3 làm việc của mình và việc của 4, 5 (mức 1×3=3), nhân viên 4, 5 không làm việc nào (mức 0).

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0