我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。
妖怪之间的基因继承关系相当简单：如果妖怪C是妖怪A和B的孩子，则C的任意一个基因只能是继承A或B的基因，继承A或B的概率各占50％。所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。
现在，我们来定义两个妖怪X和Y的基因相似程度。例如，有一个家族，这个家族中有两个毫无关系(没有相同基因)的妖怪A和B，及它们的孩子C和D。那么C和D相似程度是多少呢？因为C和D的基因都来自A和B，从概率来说，各占50％。所以，依概率计算C和D平均有50％的相同基因，C和D的基因相似程度为50％。需要注意的是，如果A和B之间存在相同基因的话，C和D的基因相似程度就不再是50％了。
你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。
共m行。可k行表示第k对妖怪之间的基因相似程度。你必须按百分比输出，有多少精度就输出多少，但不允许出现多余的0（注意，0.001的情况应输出0.1%，而不是.1%）。具体格式参见样例。
【算法分析】
本题是一道概率计算题，但这个概率计算又是建立在Family Tree模型上的。Family Tree是一个有向无环图，有明显的阶段性(辈分关系)，而且没有后效性（没有人可以成为自己的祖先），符合动态规划模型的基本条件。因此，应该可以套用类似动态规划的方法来解决。
我们先来明确一下相似程度的计算方法。假设我们要求的是A和B的相似程度（设为P(A, B)），那么有两种情况是显然的：
（1）A=B:P(A, B)=1；
（2）A与B无相同基因：P(A, B)=0。
这是计算其他复杂情况的基础。因为动态规划就是从一些特定的状态（边界条件）出发，分阶段推出其他状态的值的。
再来看一般的情况，设A0和A1是A的父母。那么，取概率平均情况，A拥有A0和A1的基因各占一半。假设A0与B的相似程度为P(A0, B)，A1与B的相似程度为P(A1, B)，那么P(A, B)与P(A0, B)和P(A1, B)之间应该是一个什么样的关系呢？很容易猜想到：
P(A, B)=(P(A0, B)+P(A1, B))/2
但是，这只是一个猜想。要让它变为一个结论还需要证明：
我们用归纳法来证明。
首先，我们知道，在这个问题中不同基因都是从特定的祖先传下来的，不会出现同一个基因采自不同的祖先的情况(注：这里的祖先是指那些没有父母的妖怪)。所以，如果A与B有相同的基因，这些基因必然来自同一个祖先。这里，我们最想说明的是，祖先那代是不存在两个人，它们之间不同的基因相同的概率不一样，因为它们相同的概率都是0。
现在，A有祖先A0和A1，A0和A1与B的相似程度分别为P(A0, B)和P(A1, B)。从祖先一代开始归纳，可由归纳假设A0与B、A1与B之间每个基因相同的概率都是一样的，分别都是P(A0, B)和P(A1, B)。A的单个基因，它可能是继承A0的，也可能是继承A1的，概率各50%。继承A0的话与B相同的概率是P(A0, B)，继承A1的话与B相同的概率是P(A1, B)。那么这个基因与B相同的概率就是：
(P(A0, B)+P(A1, B))/2
因此，A的每个基因与B相同的概率都是(P(A0, B)+P(A1, B))/2，具有相同的概率。进而，A与B相同基因的数量概率平均也为(P(A0, B)+P(A1, B))/2，A与B的相似程度 P(A, B)=(P(A0, B)+P(A1, B))/2
这样就归纳证明了P(A, B)的概率递推公式。
下面总结一下前面得出的结论：
(1)边界条件：
① A=B:P(A, B)＝1；
② A与B无相同基因：P(A, B)=0；
(2)递推关系：
P(A, B)＝(P(A0, B)+P(A1, B))/2，其中A0和A1是A的父母
有了边界条件和递推关系，以及Family Tree的阶段性和无后效性作为前提，用动态规划解决问题的所有条件都已满足。应该说，从理论上来讲，本题已经完全解决。下面需要讨论的仅仅是实现方法而已。
动态规划的实现方法有两种：一种是逆向的递推，另一种是正向的记忆化搜索（递归）。这两种方法都是可行的，区别仅仅在于，递推需要更多的考虑状态的阶段性，按照阶段计算出所有状态的值；而记忆化搜索只需要承认状态具有阶段性，无需考虑阶段，只需要按照递推式本身设计带记忆化的递归函数即可。
本题给出的仅仅是一棵Family Tree，并没有给出Family Tree的阶段，如果要用递推的话，就必须先给Family Tree分阶段（拓扑排序）。所以，本题显然更适合用记忆化搜索来实现。
另外，需要注意的是，本题所求的答案是有多少精度就输出多少精度。300个节点的图，少说也可以构成几十层的Family Tree，算出的结果至少也有小数点后几十位。所以，高精度是必不可少的（保险起见，可以设置300位的高精度）。
分析一下本题的时间复杂度。动态规划的状态有n2个，转移代价为O(C)（高精度计算的代价）。因此，时间复杂度为为O(Cn2)，n≤300。
严格的讲，本题的算法不能算动态规划的方法，因为本题不存在最优化，应该仅仅是一个递推。不过，从分析问题的过程来看，它里面包含了很多动态规划的思想，例如，阶段性和无后效性，特别是使用了动态规划的一种实现方法记忆化搜索。