결정 트리

결정 트리, 특히 분류 트리라고 불리는 유형은 항목의 특징을 사용하여 항목을 범주로 분류하는 데 사용되는 자료 구조이다. 예를 들어, 각 동물은 "cute"이거나 그렇지 않다. 주어진 어떤 동물에 대해서도, 그 동물의 특징을 살펴보고 다음 결정 트리를 사용하여 귀여운지 판단할 수 있다.

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

결정 트리는 재귀적으로 정의된다. 결정 트리에는 항상 루트 노드와 가중치가 있다. 또한 선택적으로 특징 이름과 두 개의 하위 트리가 있으며, 이 하위 트리들 자체도 결정 트리이다.

더 형식적으로, 결정 트리는 다음 문법을 사용하여 정의된다.

tree ::= (weight [feature tree tree])
weight is a real number between 0 and 1, inclusive
feature is a string of 1 or more lower case English letters

대괄호 안의 부분인 []은 선택 사항이다. 괄호 (), 가중치, 특징은 토큰이다. 여는 괄호 '(' 뒤나 닫는 괄호 ')' 앞은 예외일 수 있지만, 임의의 두 토큰 사이에는 적어도 하나의 공백 문자가 있다. 공백 문자는 스페이스 문자(' ')와 줄바꿈 문자('\n')이다.

동물이 귀여울 가능성을 알아내기 위해, 확률 p를 1로 설정하고 트리의 루트에서 시작한다. 각 노드에서 p에 그 노드의 가중치를 곱한다. 노드가 리프이면, 즉 하위 트리가 없으면 멈추며 p의 값이 해당 동물이 귀여울 확률이다. 그렇지 않으면 노드와 연관된 특징을 살펴본다. 해당 동물이 이 특징을 가지고 있으면 첫 번째 하위 트리로 내려가 재귀적으로 계속한다. 해당 동물이 이 특징을 가지고 있지 않으면 두 번째 하위 트리로 내려가 같은 방식으로 계속한다.

예를 들어, 비버는 털이 많음과 민물 서식이라는 두 가지 특징을 가진 동물이다. 루트에서 p를 1로 두고 시작한다. p에 루트의 가중치인 0.2을 곱하고, 비버가 털이 많음 특징을 가지고 있으므로 첫 번째 하위 트리로 이동한다. 그곳에서 p에 0.81을 곱하면 p는 0.162이 된다. 그다음 비버는 빠름 특징을 가지고 있지 않으므로 두 번째 하위 트리로 더 내려간다. 마지막으로 p에 0.2을 곱하면 최종적으로 0.0324을 얻는다. 이는 비버가 귀여울 확률이다.

결정 트리 하나와 특징이 함께 주어진 동물 목록이 주어진다. 각 항목에 대해 해당 동물이 귀여울 확률을 반환해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ N ≤ 100 모든 가중치는 0 이상 1 이하이다. 모든 가중치는 숫자와 최대 하나의 소수점으로만 구성된다. 가중치는 소수점으로 시작하거나 끝나지 않는다. 가중치에는 소수점 앞에 0이 둘 이상 있지 않는다. 모든 동물 이름과 특징 이름은 1개 이상 10개 이하의 영문 소문자로 구성된다. 하나의 테스트 케이스 안에서 모든 동물 이름은 서로 다르다. 한 동물의 모든 특징 이름은 서로 다르다. 결정 트리 정의를 구성하는 L개의 각 줄은 줄바꿈 문자를 제외하고 최대 80자이다.

작은 데이터 세트

1 ≤ L ≤ 10 1 ≤ A ≤ 10 0 ≤ n ≤ 5

큰 데이터 세트

1 ≤ L ≤ 100 1 ≤ A ≤ 100 0 ≤ n ≤ 100

입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 테스트 케이스의 설명은 결정 트리를 기술하는 줄의 수를 나타내는 정수 L이 포함된 줄로 시작한다. 다음 L개의 줄에는 위에서 설명한 형식의 결정 트리가 주어진다. 그다음 줄에는 동물의 수를 나타내는 A가 주어진다. 다음 A개의 각 줄에는 다음 형식으로 한 동물의 설명이 주어진다.

animal n feature_{1} feature_{2} ... feature_{n}

각 테스트 케이스마다 "Case #x:"을 포함하는 한 줄을 출력하고, 그 뒤에 동물마다 한 줄씩 입력에 등장한 순서대로 정확히 A개의 줄을 출력한다. 각 줄에는 해당 동물이 귀여울 확률을 출력해야 한다. 절대 오차 또는 상대 오차가 10^{-6} 이내인 답은 정답으로 간주된다.