루미 알고리즘

#1385골드Free food

PO 2016 결선코딩출제 Oskar Werkelin Ahlin영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Hsara loves free food.

Tonight Hsara is going out for a dinner at a restaurant with his organisation and Hsara is thinking about the chances of someone else paying for the dinner. Exactly one person will pay for the entire dinner (everyone's food), but not any person. It is only allowed to pay for dinner if no supperior (possibly indirect, for example, your boss' boss) in the organisation is present at the table.

The organisation consists of N people numbered from 1 to N. Each person, except for the CEO, has exactly one boss. Given each person's boss and a list of people present at the table, determine how many people are able to pay for the dinner.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Illustration of the organisation in the first sample.

Input

The first line consists of two integers, N - the number of people in the organisation and 1 ≤ M ≤ N - the number of people at the table.

The second line consists of N integers. The i:th integer is the boss of person i. 0 means that person i is the CEO. There will be exactly one CEO.

The third line consists of M integers indicating the people present at the table.

Output

Print an integer - the number of people at the table who would be able to pay for the dinner.

Grading

Your solution will be tested on several groups of test cases. To get points for a group you need to pass all the tests of that group.

GroupPointsConstraints
1492 ≤ N ≤ 2000
2512 ≤ N ≤ 100000.

Explanation

In the first sample person 1 and person 2 can pay. Person 3 can't pay because person 1 is at the table.

In the second sample person 5 is the CEO and at the table. Therefore only person 5 can pay.

예제

예제 1

입력
5 3
5 5 4 1 0
1 2 3
출력
2

예제 2

입력
6 5
5 4 4 5 0 1
5 1 3 2 4
출력
1

출처 표기

출처: Programmeringsolympiaden 2016년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.