시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1536 MB | 604 | 165 | 129 | 25.545% |
주식으로 엄청난 돈을 벌어들인 영욱이는 그 돈으로 나라를 세우고 나라의 통신을 담당하는 통신탑을 설치했다.
다들 알다시피 영욱이의 나라는 $N$개의 지역과 이를 잇는 $N-1$개의 도로로 이루어진 트리 형태이다. 각 지역에는 $1$번부터 $N$번까지의 번호가 붙어 있다. $1$번 지역이 영욱이가 살고 있는 지역으로, 이 나라의 수도이자 트리의 루트이다. 영욱이의 나라의 각 지역에는 통신탑이 하나씩 있어서, 트리에서 조상과 자손 관계인 두 지역의 통신탑끼리 정보를 교환할 수 있다.
그러나 이를 본 적국의 다니엘이 통신방해전파를 쏘아올리기 시작했다! 통신방해전파 때문에 이제 일부 통신탑끼리만 통신을 할 수 있게 되었다. 통신탑에는 주파수가 하나씩 배정되어 있는데, 주파수가 서로 약수 또는 배수 관계인 통신탑끼리만 통신을 할 수 있다.
우리는 영욱이의 나라에서 통신이 가능한 서로 다른 두 통신탑 쌍의 개수를 구해야 한다. 단, 다른 통신탑을 거쳐서 간접적으로 통신하는 것은 허용되지 않는다.
첫 번째 줄에 영욱이의 나라를 구성하는 지역의 개수 $N$이 주어진다.
두 번째 줄에 영욱이의 나라의 $1, \cdots, N$번 지역에 있는 통신탑의 주파수 $A[i]$가 각각 주어진다.
세 번째 줄에는 $i$번 지역의 부모 노드에 위치한 지역의 번호 $P[i]$가 $i=2, \cdots, N$에 대해 순서대로 주어진다.
통신이 가능한 서로 다른 두 통신탑 쌍의 개수를 구하여 출력한다.
4 1 2 3 4 1 2 2
4
Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2020! E번