바이러스와 안티바이러스
시간 제한2초메모리 제한1024 MB
같은 N명의 직원에 대한 두 개의 루트 트리가 주어질 때, 두 트리 모두에서 A가 B의 조상인 순서쌍 (A, B)의 개수를 센다.
문제
한 안티바이러스 IT 회사에는 공식적인 계층형 관리 구조가 있다. 이 구조에는 상사가 없는 유일한 직원인 보스가 있다. 나머지 직원은 각각 정확히 한 명의 직원, 즉 자기 상사의 부하이다. 상사는 여러 부하를 둘 수 있으며 그중 누구에게든 명령을 내리거나 전달할 수 있다. 명령은 한 직원에서 다른 직원으로 상사에서 부하로 이어지는 사슬을 따라서만 전달될 수 있다.
이 계층에서 직원 A는 직원 B보다 높다고 한다. A가 B에게 직접 또는 부하의 사슬을 거쳐 명령을 내리거나 전달할 수 있으면 그렇다. 보스는 모든 직원보다 높다.
그런데 모든 직원은 컴퓨터 바이러스를 만드는, 비슷한 방식으로 조직된 또 하나의 비밀 계층 구조에도 속해 있다. 비밀 구조에는 다른 보스가 있을 수 있고, 직원에게는 다른 상사가 있을 수 있다.
직원 쌍 A, B를 안정적이라고 부르는 것은 A가 기본 계층 구조와 비밀 계층 구조 모두에서 B보다 높은 경우이다. 회사에 있는 안정적인 쌍의 수를 구하는 프로그램을 작성해야 한다.
입력
첫째 줄에 회사의 직원 수 N이 주어진다. (1 ≤ N ≤ 100 000)
둘째 줄에 N개의 정수 ai가 주어진다. ai = 0이면 공식 계층에서 번호 i인 직원이 보스이고, 그렇지 않으면 ai는 번호 i인 직원의 직속 상사 번호이다.
셋째 줄에 N개의 정수 bi가 주어진다. bi = 0이면 비밀 계층에서 번호 i인 직원이 보스이고, 그렇지 않으면 bi는 번호 i인 직원의 직속 상사 번호이다.
직원 번호는 입력 파일에 나온 순서대로 1부터 매긴다.
출력
출력 파일에는 안정적인 쌍의 수 하나만 있어야 한다.
힌트
이 문제에는 세 개의 부분 문제가 있다. 각 부분 문제의 점수는 해당 테스트 묶음으로 매긴다. 부분 문제의 점수는 그 묶음의 모든 테스트를 통과한 경우에만 주어진다.