P1235 Blood Relationship

We are studying the blood relationships within a family of yaoguai (妖怪, yaoguai). Each yaoguai has the same number of genes, but the genes of different yaoguai may differ. We want to know how many genes are the same between any two given yaoguai. Since the number of genes is massive, direct testing is not feasible. However, we know the family tree, so we can estimate the number of shared genes between two yaoguai based on the family tree. The inheritance of genes among yaoguai is quite simple: if yaoguai $C$ is the child of yaoguai $A$ and $B$, then any single gene of $C$ can only be inherited from either $A$ or $B$, with a $50\%$ probability for each. All genes are considered independent, and the inheritance of any gene is not affected by other genes. Now, we define the gene similarity between two yaoguai $X$ and $Y$. For example, consider a family with two unrelated yaoguai $A$ and $B$ (no shared genes), and their children $C$ and $D$. What is the similarity between $C$ and $D$? Since the genes of $C$ and $D$ both come from $A$ and $B$, each with a probability of $50\%$, in expectation $C$ and $D$ share $50\%$ of their genes, so the gene similarity between $C$ and $D$ is $50\%$. Note that if $A$ and $B$ have shared genes, then the similarity between $C$ and $D$ will no longer be $50\%$. Your task is to write a program that, given the family tree and several pairs of yaoguai, computes their gene similarity.

The first line contains two integers $n\ (2 \le n \le 300)$ and $k$. Here $n$ is the number of members in the family, labeled $1,2,\cdots,n$. $k\ (0 \le k \le n-2)$ is the number of yaoguai in this family who have parents (the remaining yaoguai have no parents given; they can be regarded as unrelated to each other, i.e., sharing no genes). The next $k$ lines each contain three integers $a, b, c$, meaning yaoguai $a$ is the child of yaoguai $b$ and $c$. Then a line with one integer $m$ ($1 \le m \le n^2$), the number of yaoguai pairs for which the gene similarity is to be computed. The next $m$ lines each contain two integers, representing a pair of yaoguai whose gene similarity should be computed. You may assume the given family tree is always valid. Specifically, no yaoguai will be an ancestor of themself, and you do not need to worry about gender inconsistencies.

Output $m$ lines. The $i$-th line corresponds to the gene similarity of the $i$-th pair of yaoguai. You must output it as a percentage, with as much precision as there actually is, and it must be exact, but do not print extra trailing $0$s. Also, a leading zero before the decimal point is required (note that for $0.001$ you should output $\verb!0.1%!$, not $\verb!.1%!$). See the sample for the exact format.

Translated by ChatGPT 5