진화 알고리즘

Ada는 학교 과학 프로젝트를 진행하고 있다. 그녀는 진화를 연구하고 있으며, 서로 다른 생물 종들이 코딩 대회 문제를 풀려고 할 때 어떤 성과를 내는지 비교하고자 한다.

$\mathbf{N}$개의 종에는 $1$ 이상 $\mathbf{N}$ 이하의 정수로 번호가 매겨져 있다. 종 $1$에는 직계 조상이 없으며, 다른 모든 종에는 자신이 직접 진화해 나온 직계 조상이 정확히 하나씩 있다. 종 $x$의 (반드시 직계일 필요는 없는) 조상이란, 종 $x$에서 시작하여 한 번 이상 현재 종의 직계 조상으로 이동함으로써 $x$에서 $y$에 도달할 수 있게 하는 다른 종 $y$를 말한다. 따라서 종 $1$은 다른 모든 종의 (직계 또는 간접) 조상이다.

복잡한 유전 시뮬레이션을 통해, 그녀는 $\mathbf{N}$개 종 각각이 특정 코딩 대회에서 받을 평균 점수를 계산했다. $\mathbf{S_i}$는 종 $i$의 평균 점수이다.

Ada는 발표에서 소개할 흥미로운 삼중항을 찾고 있다. 흥미로운 삼중항은 다음 조건을 만족하는 서로 다른 종들의 순서 있는 삼중항 $(a, b, c)$로 정의한다.

• 종 $b$은 종 $a$의 (직계 또는 간접) 조상이다.

• 종 $b$은 종 $c$의 (직계 또는 간접) 조상이 아니다.

• 종 $b$의 평균 점수는 $a$와 $c$의 평균 점수 둘 다보다 엄격히 $\mathbf{K}$배를 초과하여 높다. 즉, $\mathbf{S_b} \ge \mathbf{K} \times \max(\mathbf{S_a}, \mathbf{S_c}) + 1$이다.

종들의 점수와 조상 관계가 주어질 때, 흥미로운 삼중항의 총개수를 세는 프로그램을 작성하여 Ada를 도와주자.

제한

시간 제한: 40초. 메모리 제한: 2 GB. $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 (Visible Verdict)

$3 \le \mathbf{N} \le 1000$.

테스트 세트 2 (Hidden Verdict)

최대 30개의 케이스에 대해: $3 \le \mathbf{N} \le 2 \times 10^5$. 나머지 케이스에 대해: $3 \le \mathbf{N} \le 1000$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 종의 수와 흥미로운 삼중항을 결정하는 계수를 각각 나타내는 두 정수 $\mathbf{N}$와 $\mathbf{K}$가 주어진다. 각 테스트 케이스의 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}$가 주어지며, 여기서 $\mathbf{S_i}$는 종 $i$의 평균 점수를 나타낸다. 각 테스트 케이스의 세 번째 줄에는 $\mathbf{N}-1$개의 정수 $\mathbf{P_2}, \mathbf{P_3}, \dots, \mathbf{P_N}$가 주어지며, 이는 종 $\mathbf{P_i}$이 종 $i$의 직계 조상임을 의미한다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Ada의 정의에 따른 흥미로운 삼중항의 총개수이다.

예제 케이스 #1에서 가능한 흥미로운 삼중항은 $(5, 3, 4)$ 하나뿐이다. 실제로 다음을 확인할 수 있다.

• 종 $b = 3$은 종 $a = 5$의 조상이다.

• 종 $b = 3$은 종 $c = 4$의 조상이 아니다.

• 종 $b = 3$의 점수는 $a = 5$와 $c = 4$의 점수 둘 다보다 $\mathbf{K}$배를 초과하여 높다: $6 = \mathbf{S_3} \ge \mathbf{K} \times \max(\mathbf{S_4}, \mathbf{S_5}) + 1 = 2 \times \max(2, 2) + 1 = 5$.

예제 케이스 #2에는 흥미로운 삼중항이 일곱 개 있다.

• $(4, 3, 1)$

• $(4, 3, 6)$

• $(4, 7, 1)$

• $(4, 7, 5)$

• $(4, 7, 6)$

• $(5, 3, 1)$

• $(5, 3, 6)$