P13434 [GCJ 2009 #1B] Decision Tree

决策树——尤其是一种被称为分类树（**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$，这就是河狸“可爱”的概率。 你将获得一棵决策树和若干动物及其特征。对于每个动物，你需要输出其被判定为“可爱”的概率。

输入的第一行为一个整数 $N$，表示测试用例数。接下来是 $N$ 组测试数据。 每组测试数据的开头是一行，包含整数 $L$，表示描述决策树的行数。接下来的 $L$ 行给出决策树的定义，格式如上所述。再下一行是整数 $A$，表示动物的数量。接下来 $A$ 行，每行描述一种动物，格式如下： $\text{animal}\ n\ \text{feature}_1 \ \text{feature}_2 \ \dots \text{feature}_n$

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

**限制条件** - $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 完成。