20532번 - 정점 간 통신 네트워크

문제

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

다들 알다시피 영욱이의 나라는 $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$)
• 모든 입력은 정수.

힌트