410323: GYM104009 G Genetics

One day, Johnny finds out he has a rare genetic condition. Naturally, he looks around the internet for a bit, and discovers that it's a condition that only affects men and it's mainly carried on the Y chromosome. After doing more research, he finds the following: A male is identified by one X chromosome and one Y chromosome (i.e. XY), while a female is identified by two X chromosomes (i.e. XX). During reproduction, when the zygote is formed, it gets a random chromosome from the mother and a random one from the father (these chromosomes being chosen with equal probability). If a chromosome carrying the disease is passed down from the parent to the child, then the child will carry the disease on that chromosome. Both males and females can carry the genetic condition on either of the chromosomes (or even on both), but it only manifests in males. In order for the disease to manifest the male must carry the disease on both of his chromosomes (i.e. both X and Y must have the gene), otherwise he is only a carrier.

Curious about the prevalence of this disease in his family, he starts wondering what is the probability of a given family member to have this disease.

Given a family tree that only has the paternal side (all nodes represent men in the family), the node that Johnny represents in his family tree, and a list of family members that Johnny is checking, your task is to calculate for each of these men their probability to have the genetic disease. Additionally, all children of a father have the same mother.

We consider that all possible chromosome combinations have a uniform distribution. The probability of a node having the disease should be calculated GIVEN the fact that you know Johnny has the disease.

Since the input and output are quite large, we recommend using fast methods of reading and writing, such as desynchronization in C++.

The first line of the input consists of the integer $$$N$$$ (the number of men in the family tree, $$$1 \leq N \leq 10^{6}$$$) and an integer $$$G$$$ ($$$1 \leq G \leq N$$$), representing Johnny.

Then, there are $$$N$$$ lines describing the children of every node. The first number, $$$n_k$$$ represents the node, and the second number, $$$c_k$$$ the number of children ($$$1 \leq c_k \leq N$$$). Then, there are $$$c_k$$$ integers, the indexes of $$$n_k$$$'s children.

On the next line is a single integer, $$$Q$$$ ($$$1 \leq Q \leq 10^{6}$$$), the number of queries.

On the final line, there's $$$Q$$$ integers, the nodes for which you need to output the probability of having the disease.

In your output, there should be $$$Q$$$ lines, the answer to every query with a precision of at least $$$10^{-7}$$$.

5 4
1 2 2 3
2 1 4
3 1 5
4 0
5 0
2
2 4

0.5000000000
1.0000000000