아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

공짜 저녁

면접 대비

시간 제한1초메모리 제한1024 MB

요약
조직의 각 구성원의 상사를 트리로 주고 식탁에 있는 사람 목록이 주어질 때, 식탁에 함께 있는 상사가 없는 사람의 수를 센다.
난이도

보통10점 중 4점

유형
트리, DFS, 해시맵, 구현
정답자
아직 제출이 없습니다

문제

오늘 밤 Hsara는 회사 사람들과 함께 식당에 저녁을 먹으러 간다. Hsara는 다른 누군가가 저녁값을 내 줄 가능성을 생각하고 있다. 저녁값은 정확히 한 사람이 전부(모두의 음식값)를 낸다. 아무나 낼 수 있는 것은 아니다. 조직에서 자신보다 높은 사람(간접적인 상사도 포함한다. 예를 들어 상사의 상사)이 식탁에 있으면 저녁값을 낼 수 없다.

조직은 NN명의 사람으로 이루어져 있고 각각 11번부터 NN번까지 번호가 붙어 있다. CEO를 제외한 모든 사람은 상사가 정확히 한 명 있다. 각 사람의 상사와 식탁에 있는 사람 목록이 주어질 때, 저녁값을 낼 수 있는 사람이 몇 명인지 구하라.

그림 1: 첫 번째 예제의 조직을 나타낸 그림.

입력

첫째 줄에 두 정수 NN과 MM이 주어진다. NN은 조직에 있는 사람 수이고, MM은 식탁에 있는 사람 수이며 1≤M≤N1 \le M \le N이다.

둘째 줄에 NN개의 정수가 주어진다. ii번째 정수는 ii번 사람의 상사이다. 0은 ii번 사람이 CEO라는 뜻이다. CEO는 정확히 한 명이다.

셋째 줄에 식탁에 있는 사람을 나타내는 MM개의 정수가 주어진다.

출력

식탁에 있는 사람 중 저녁값을 낼 수 있는 사람 수를 정수로 출력한다.

제한

  • 2≤N≤100 0002 \le N \le 100\,000

힌트

첫 번째 예제에서는 1번과 2번 사람이 낼 수 있다. 3번 사람은 1번 사람이 식탁에 있으므로 낼 수 없다.

두 번째 예제에서는 5번 사람이 CEO이고 식탁에 있다. 따라서 5번 사람만 낼 수 있다.

예제2

  1. 예제 1

    입력
    5 3
    5 5 4 1 0
    1 2 3
    
    예상 출력
    2
    
  2. 예제 2

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