승현이의 하드 디스크에는 파일이 너무 많습니다.(?) 매일 이를 못마땅해하던 승현이는 드디어 오늘, 파일들을 정리하려고 합니다.
이 하드디스크의 파일 구조는 계층 트리 구조로, N개의 파일과 M개의 디렉토리로 구성되어 있습니다.
0부터 N - 1까지의 번호가 붙어 있습니다.0부터 M - 1까지의 번호가 붙어 있습니다. 위 그림에서 원으로 표현되어 있습니다. 예로 들어, 3번 디렉토리는 2, 3, 4번 파일을 포함하고, 4번 디렉토리는 6번 파일과 5번 디렉토리(총 3개의 파일)를 포함합니다.안타깝게도, 파일을 삭제하는 명령어는 아래 2가지밖에 없습니다.
del_file n : n번 파일을 삭제합니다. (단, n은 0 이상 N - 1 이하의 정수)del_dir d : d번 디렉토리를 삭제합니다. (단, d은 0 이상 M - 1 이하의 정수) 당연하지만, d번 디렉토리를 삭제한 이후 d번 디렉토리의 하위 파일 또는 디렉토리를 삭제할 수 없습니다.예로 들어 위 그림에서 "del_dir 4" 명령어를 실행하면, 4번 디렉토리 하위의 모든 파일 또는 디렉토리(여기서는 6번, 7번, 8번 파일과 4번, 5번 디렉토리)가 삭제됩니다.
승현이는 자신의 하드 디스크에서 정확히 K개의 파일 (디렉토리는 파일이 아닙니다!)을 삭제하려고 합니다. 명령어는 사람이 직접 입력해야 하기 때문에, 승현이는 얼마나 많은 시간을 들일지 미리 예상하려고 합니다.(?) 예로, 위 그림에서 K = 4라고 가정하면 "del_dir 4", "del_file 5" 와 같이 2번의 명령어로 4개의 파일을 삭제할 수 있으며, 이 경우보다 더 적은 명령어 수로 4개의 파일을 삭제할 수 없습니다.
승현이의 하드 디스크 구조가 주어질 때, K개의 파일을 삭제하기 위해 사용해야 할 최소한의 명령어 수를 구하는 프로그램을 작성하세요.
첫 번째 줄에 승현이의 하드 디스크에 있는 파일의 수 N, 디렉토리의 수 M, 그리고 삭제해야 할 파일의 개수 K가 공백을 사이로 두고 주어집니다.
두 번째 줄에 A[0], A[1], .., A[N - 1]이 공백을 사이로 두고 주어집니다. 임의의 i(0 ≤ i ≤ N - 1)에 대해 A[i]번 디렉토리는 i번 파일의 부모 디렉토리입니다.
세 번째 줄에 B[0], B[1], .., B[M - 1]이 공백을 사이로 두고 주어집니다. 임의의 i(1 ≤ i ≤ M - 1)에 대해 B[i]번 디렉토리는 i번 디렉토리의 부모 디렉토리입니다. 단, 0번 폴더는 루트 디렉토리이므로, B[0] = -1입니다.
첫 번째 줄에 K개의 파일을 삭제하기 위해 승현이가 입력해야 할 최소한의 명령어 수를 출력합니다.
1 ≤ K ≤ N ≤ 10 000, 1 ≤ M ≤ 3 000
입력 9 6 4 2 2 3 3 3 0 4 5 5 -1 0 1 1 0 4 출력 2
출처: GENIUSainta.com