ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#10460

진화 알고리즘 40s 2048MB

問題

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

\mathbf{N}개의 종은 1부터 \mathbf{N}까지의 정수로 번호가 매겨져 있다. 종 1은 직접 조상이 없고, 나머지 모든 종은 각각 정확히 한 명의 직접 조상을 가지며 그로부터 직접 진화했다. 종 x의 조상(직접 조상일 필요는 없음)이란, 종 x에서 시작해 직접 조상으로 한 번 이상 반복해서 이동했을 때 도달할 수 있는 다른 종 y를 말한다. 이런 정의에 따라, 종 1은 다른 모든 종의 (직접 또는 간접) 조상이다.

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

에이다는 발표에서 보여 줄 흥미로운 삼중쌍(interesting triplets)을 찾고 있다. 흥미로운 삼중쌍은 서로 다른 세 종의 순서 있는 삼중쌍 (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{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는 에이다의 정의에 따른 흥미로운 삼중쌍의 총 개수이다.


例題 

2
5 2
3 3 6 2 2
3 1 1 3
7 3
2 4 7 2 2 1 8
6 1 7 3 1 3
Case #1: 1
Case #2: 7
샘플 케이스 #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에서는 흥미로운 삼중쌍이 7개 있다: (4, 3, 1) (4, 3, 6) (4, 7, 1) (4, 7, 5) (4, 7, 6) (5, 3, 1) (5, 3, 6)

出典

GCJ 2023c C

ログインしないとコードを書けません。