Genealogical Gene Similarity in Monster Families

In this problem, we study the genetic similarity between monsters belonging to a family. Every monster has the same number of genes but the gene types might differ among monsters. Given a family tree (genealogy) and a series of queries, for each pair of monsters you must compute the probability that a randomly chosen gene from both monsters is the same.

The genetic inheritance follows a simple rule: If monster \(C\) is the child of monsters \(A\) and \(B\), then for every gene, \(C\) inherits the gene from \(A\) with probability \(50\%\) and from \(B\) with probability \(50\%\). All genes are independent of each other. In addition, if two monsters are both founders (i.e. they have no recorded parents) then they are considered to have completely distinct genes (i.e. similarity 0) unless they are the same monster (in which case, similarity is 100%).

For monsters that are not founders, the genetic similarity \(f(X, Y)\) between any two monsters \(X\) and \(Y\) is defined recursively as follows. Let \(P(X)\) denote the two parents of \(X\) (if \(X\) is not a founder). Then:

• If \(X = Y\), then \(f(X, Y) = 1\).
• If both \(X\) and \(Y\) are founders and \(X \neq Y\), then \(f(X, Y) = 0\).
• If one of \(X\) or \(Y\) is a founder and the other is not, assume without loss of generality that \(X\) is not a founder with parents \(A\) and \(B\), then \( f(X, Y) = \frac{f(A, Y) + f(B, Y)}{2} \).
• If both \(X\) and \(Y\) are non-founders with parents \(A, B\) and \(C, D\) respectively, then \[ f(X, Y) = \frac{f(A, C) + f(A, D) + f(B, C) + f(B, D)}{4}. \]

You are given the family tree and several queries (each consisting of a pair of monster names). For each query, output the genetic similarity (as a floating-point number) between the two monsters. Output the answer with 6 decimal places.

inputFormat

The input begins with an integer \(n\) representing the number of monsters.

 n
 monster_name parent1 parent2
 monster_name parent1 parent2
 ...

For a founder monster (i.e. one with no parents), both parent values will be given as 0.

The next line contains an integer \(q\), the number of queries.

 q
 monster_name_1 monster_name_2
 monster_name_1 monster_name_2
 ...

outputFormat

For each query, print a line containing the genetic similarity between the two monsters as a floating point number with 6 decimal places.

sample

4
A 0 0
B 0 0
C A B
D A B
1
C D

0.500000