Description

决策树——尤其是一种被称为分类树（classification trees）的类型——是一种用于根据物品的特征将其分类的数据结构。例如，每只动物要么“可爱”，要么不可爱。对于任意一只动物，我们可以通过观察其特征，并使用如下决策树来判断它是否可爱。

(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 是一个在 0 到 1 之间（含 0 和 1）的实数
feature 是由一个或多个小写英文字母组成的字符串

方括号 [] 内的部分为可选项。圆括号 ()、权重和特征都是标记。任意两个标记之间至少有一个空白字符（空格 ' ' 或换行符 '\n'），但在左括号 '(' 后或右括号 ')' 前可能没有空白。每一行的长度（不包括换行符）不会超过 80 个字符。

为了判断一只动物有多大概率是可爱的，我们从树的根节点开始，初始概率 $p=1$。在每个节点，我们将 $p$ 乘以该节点的权重。如果该节点是叶子节点（没有子树），则停止，当前 $p$ 的值即为该动物可爱的概率。否则，查看该节点关联的特征。如果动物具有该特征，则进入第一棵子树递归处理；否则进入第二棵子树递归处理。

例如，河狸（beaver）有两个特征：furry 和 freshwater。我们从根节点开始，$p=1$，乘以根节点的权重 $0.2$，进入第一棵子树（因为河狸有 furry 特征）。在该子树中，再乘以 $0.81$，$p$ 变为 $0.162$。接着，因为河狸没有 fast 特征，进入第二棵子树。再乘以 $0.2$，最终得到 $0.0324$，这就是河狸“可爱”的概率。

你将获得一棵决策树和若干动物及其特征。对于每个动物，你需要输出其被判定为“可爱”的概率。

Input Format

输入的第一行为一个整数 $N$，表示测试用例数。接下来是 $N$ 组测试数据。

每组测试数据的开头是一行，包含整数 $L$，表示描述决策树的行数。接下来的 $L$ 行给出决策树的定义，格式如上所述。再下一行是整数 $A$，表示动物的数量。接下来 $A$ 行，每行描述一种动物，格式如下：

$\text{animal}\ n\ \text{feature}_1 \ \text{feature}_2 \ \dots \text{feature}_n$

Output Format

对于每组测试数据，输出一行 "Case #x:"，接着输出 $A$ 行，每行一个概率，顺序与输入动物顺序一致。每个概率保留至少 7 位小数。只要你的答案的绝对误差或相对误差不超过 $10^{-6}$，即视为正确。

1
3
(0.5 cool
  ( 1.000)
  (0.5 ))
2
anteater 1 cool
cockroach 0

Case #1:
0.5000000
0.2500000

Hint

限制条件

• $1 \leq N \leq 100$
• 所有权重均为 $[0, 1]$ 区间内的实数。
• 权重仅包含数字和最多一个小数点。
• 权重不会以小数点开头或结尾。
• 权重在小数点前不会有超过一个 0。
• 所有动物名和特征名均为 1 到 10 个小写英文字母。
• 每组测试数据内所有动物名互不相同。
• 单个动物的所有特征互不相同。
• 决策树定义的每一行长度不超过 80 个字符（不含换行符）。

小数据集（10 分）

• $1 \leq L \leq 10$
• $1 \leq A \leq 10$
• $0 \leq n \leq 5$

大数据集（11 分）

• $1 \leq L \leq 100$
• $1 \leq A \leq 100$
• $0 \leq n \leq 100$

翻译由 ChatGPT-4.1 完成。