진화 알고리즘

Ada는 학교 과학 프로젝트를 준비하고 있다. 그녀는 진화를 연구하며, 서로 다른 종의 생물이 코딩 대회 문제를 얼마나 잘 푸는지 비교하고 싶어 한다.

종은 1부터 $\mathbf{N}$까지 번호가 매겨져 있다. 1번 종은 직접 조상이 없고, 나머지 모든 종은 직접 조상이 정확히 한 명씩 있으며 그 조상으로부터 진화했다. 종 $x$의 조상(직접 또는 간접)은 $x$에서 직접 조상으로 거슬러 올라가 도달할 수 있는 다른 종 $y$이다. 따라서 1번 종은 다른 모든 종의 조상이다.

각 종 $i$는 어떤 코딩 대회에서의 평균 점수 $\mathbf{S\_i}$를 가진다. Ada는 이 점수들을 유전 시뮬레이션으로 계산했다.

흥미로운 세쌍은 다음 조건을 만족하는 서로 다른 종의 순서쌍 $(a, b, c)$이다.

1. 종 $b$는 종 $a$의 조상이다.
2. 종 $b$는 종 $c$의 조상이 아니다.
3. 종 $b$의 평균 점수가 $a$와 $c$의 점수보다 $\mathbf{K}$배 넘게 크다. 즉 $\mathbf{S\_b} \ge \mathbf{K} \times \max(\mathbf{S\_a}, \mathbf{S\_c}) + 1$이다.

흥미로운 세쌍의 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $\mathbf{T}$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 두 정수 $\mathbf{N}$과 $\mathbf{K}$가 주어진다.

둘째 줄에 $\mathbf{N}$개의 정수 $\mathbf{S\_1}, \mathbf{S\_2}, \dots, \mathbf{S\_N}$이 주어진다.

셋째 줄에 $\mathbf{N}-1$개의 정수 $\mathbf{P\_2}, \mathbf{P\_3}, \dots, \mathbf{P\_N}$이 주어진다. $\mathbf{P\_i}$는 종 $i$의 직접 조상이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 흥미로운 세쌍의 총 개수이다.

• $1 \le \mathbf{T} \le 100$.
• $1 \le \mathbf{K} \le 10^9$.
• 모든 $i$에 대해 $1 \le \mathbf{S\_i} \le 10^9$.
• 모든 $i$에 대해 $1 \le \mathbf{P\_i} \le \mathbf{N}$.
• 1번 종은 다른 모든 종의 (직접 또는 간접) 조상이다.

예제 1번에서 흥미로운 세쌍은 $(5, 3, 4)$ 하나뿐이다. 종 3은 종 5의 조상이고, 종 4의 조상은 아니다. 또한 $6 = \mathbf{S\_3} \ge \mathbf{K} \times \max(\mathbf{S\_4}, \mathbf{S\_5}) + 1 = 2 \times \max(2, 2) + 1 = 5$이다.

예제 2번에서 흥미로운 세쌍은 모두 7개이다.

• $(4, 3, 1)$
• $(4, 3, 6)$
• $(4, 7, 1)$
• $(4, 7, 5)$
• $(4, 7, 6)$
• $(5, 3, 1)$
• $(5, 3, 6)$