Quản lí công ty 2

View as PDF

Submit solution

Points: 0.95 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

yenthanh132 hiện đang là giám đốc của Attosoft (micro = ~10^{-6}~, atto = ~10^{-18}~), công ty phần mềm lớn nhất vương quốc C11. Công ty có ~N~ nhân viên, được đánh số từ ~1~ đến ~N~ và yenthanh132 là người được đánh số ~1~. Mỗi người ngoại trừ yenthanh132 có đúng một sếp. Nếu ~z~ dưới quyền quản lí của nhân viên ~y~ và ~y~ dưới quyền quản lí của ~x~ thì ~z~ dưới quyền quản lí của ~x~. Tất cả ~N-1~ nhân viên còn lại trong công ty đều dưới quyền quản lí của yenthanh132.

Mỗi nhân viên trong công ty chuyên về một loại ngôn ngữ lập trình nhất định. Có tất cả ~M~ ngôn ngữ lập trình khác nhau được đánh số từ ~1~ đến ~M~.

Mỗi khi nhận một đơn đặt hàng viết phần mềm gửi cho nhân viên ~u_{i}~ nào đó, nhân viên ~u_{i}~ này phải chọn ra trong số các nhân viên mà mình quản lí (kể cả mình), từ ~1~ đến ~K~ người cùng chuyên môn về một ngôn ngữ lập trình nào đó để viết phần mềm. Vấn đề đặt ra ở đây là yenthanh132 muốn biết xem với mỗi yêu cầu như vậy thì có bao nhiêu ngôn ngữ lập trình khác nhau mà trong số nhân viên ~u_{i}~ và các nhân viên mà ~u_{i}~ quản lí , có ít nhât một người và không quá ~K~ người chuyên môn về ngôn ngữ lập trình đó.

Yêu cầu: Hãy giúp yenthanh132 trả lời xem nếu có một đơn đặt hàng gửi cho nhân viên ~u_{i}~ thì sẽ có bao nhiêu ngôn ngữ lập trình khác nhau thỏa điều kiện đã nêu ở trên

Input

  • Dòng đầu tiên chứa ~3~ số nguyên ~N~, ~M~, ~K~ lần lượt là số nhân viên trong công ty, số lượng ngôn ngữ lập trình khác nhau, và số lượng nhân viên trong một cách chọn.
  • ~N-1~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~p_{i+1}~ là sếp của nhân viên thứ ~i+1~.
  • Dòng thứ ~N+1~ chứa ~N~ số nguyên ~v_{1}~, ~v_{2}~, ...~v_{n}~. Trong đó ~v_{i}~ là ngôn ngữ lập trình chuyên môn của nhân viên ~i~. ~(1 \le v_{i} \le M)~
  • Dòng thứ ~N+2~ chứa số nguyên ~Q~, là số truy vấn.
  • ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~u_{i}~ ~(1 \le u_{i} \le N)~

Output

  • Gồm ~Q~ dòng, dòng thứ ~i~ là số ngôn ngữ lập trình khác nhau thỏa yêu cầu khi có một đơn đặt hàng gửi cho nhân viên ~u_{i}~.

Giới hạn

  • Trong ~20\%~ số test có ~1 \le N~, ~Q~, ~K \le 1000~.
  • Trong tất cả các test: ~1 \le N~, ~Q~, ~K \le 10^{5}~
  • ~1 \le M \le 10^{5}~
  • ~1 \le K \le N~

Sample Input

10 4 2
1
2
2
3
3
1
7
7
7
1 2 4 3 2 4 4 3 3 3
4
1
2
7
3

Sample Output

2
3
1
2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.