시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1536 MB 360 96 81 27.273%

문제

주식으로 엄청난 돈을 벌어들인 영욱이는 그 돈으로 나라를 세우고 나라의 통신을 담당하는 통신탑을 설치했다.

다들 알다시피 영욱이의 나라는 $N$개의 지역과 이를 잇는 $N-1$개의 도로로 이루어진 트리 형태이다. 각 지역에는 $1$번부터 $N$번까지의 번호가 붙어 있다. $1$번 지역이 영욱이가 살고 있는 지역으로, 이 나라의 수도이자 트리의 루트이다. 영욱이의 나라의 각 지역에는 통신탑이 하나씩 있어서, 트리에서 조상과 자손 관계인 두 지역의 통신탑끼리 정보를 교환할 수 있다.

그러나 이를 본 적국의 다니엘이 통신방해전파를 쏘아올리기 시작했다! 통신방해전파 때문에 이제 일부 통신탑끼리만 통신을 할 수 있게 되었다. 통신탑에는 주파수가 하나씩 배정되어 있는데, 주파수가 서로 약수 또는 배수 관계인 통신탑끼리만 통신을 할 수 있다.

우리는 영욱이의 나라에서 통신이 가능한 서로 다른 두 통신탑 쌍의 개수를 구해야 한다. 단, 다른 통신탑을 거쳐서 간접적으로 통신하는 것은 허용되지 않는다.

입력

첫 번째 줄에 영욱이의 나라를 구성하는 지역의 개수 $N$이 주어진다.

두 번째 줄에 영욱이의 나라의 $1, \cdots, N$번 지역에 있는 통신탑의 주파수 $A[i]$가 각각 주어진다.

세 번째 줄에는 $i$번 지역의 부모 노드에 위치한 지역의 번호 $P[i]$가 $i=2, \cdots, N$에 대해 순서대로 주어진다.

출력

통신이 가능한 서로 다른 두 통신탑 쌍의 개수를 구하여 출력한다.

제한

  • $1 \leq N \leq 100\,000$
  • $1 \leq A[i] \leq 100\,000$ ($1 \leq i \leq N$)
  • $1 \leq P[i] < i$ ($2 \leq i \leq N$)
  • 모든 입력은 정수.

예제 입력 1

4
1 2 3 4
1 2 2

예제 출력 1

4

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2020! E번