진화 알고리즘 timer 40s memory 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이어야 한다.

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