Norton’s Magnetic Cave Quest

Norton finds himself in a cave system that can be modeled as a tree with \(n\) nodes (caves) and \(n-1\) edges (tunnels). Norton starts at a cave \(s\), and the treasure is located at a cave \(t\). In cave \(t\) there is a unique special magnet with a fixed pole \(c_2\) (either N or S). Norton also carries a small magnet which initially has pole \(c_1\). At the beginning of each time step (unless stunned as explained below) Norton’s magnet may flip with probability \(p\) (i.e. N becomes S and S becomes N).

The movement is determined by the two magnets as follows (with the tree re‐rooted at the treasure cave \(t\)):

• Attraction: If Norton’s magnet and the treasure’s magnet have different poles, then Norton is attracted. He deterministically moves to the unique adjacent cave that is one step closer to \(t\) (i.e. the parent of his current cave).
• Repulsion: If the two magnets have the same pole, then Norton is repelled. He will move, with equal probability, to one of the adjacent caves that is one step further from \(t\) (i.e. one of the children of his current cave). However, if there is no such cave (i.e. his current cave is a leaf in the tree rooted at \(t\)), a stun effect triggers: he does not move, and in the next time step he neither flips his magnet nor moves.

Assuming Norton knows the entire cave structure and the flipping probability \(p\), he will ask you many queries. In each query, given that he starts from cave \(x\) with magnet pole \(c_1\) and the treasure is at cave \(y\) with fixed magnet pole \(c_2\), compute the expected number of time steps until Norton finds the treasure. (If \(x=y\), the answer is 0.)

The formulas used in the analysis are displayed in \(\LaTeX\) format. For example, if Norton is in a leaf cave (other than \(t\)) and his magnet pole equals \(c_2\), then his expected value satisfies the equation:

[ E(v, c_2) = 1 + (1-p)(1 + E(v, c_2)) + p,E(u, \overline{c_2}), ]

which can be rearranged to

[ p,E(v, c_2) = 1 + (1-p) + p,E(u, \overline{c_2}), \quad \text{or} \quad E(v, c_2) = \frac{2-p}{p} + E(u, \overline{c_2}). ]

</p>

For non‐leaf caves and for the case when Norton’s magnet pole differs from \(c_2\), similar linear equations can be set up. You are to solve these systems (the total number of unknowns is \(2(n-1)\)) for each query.

inputFormat

The input begins with a line containing two numbers: an integer \(n\) (the number of caves) and a real number \(p\) (the magnet flip probability, \(0<p\le 1\)).

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating there is a tunnel between cave \(u\) and cave \(v\). The caves are numbered from 1 to \(n\).

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

Each of the following \(q\) lines contains a query in the form:
\(x\ c_1\ y\ c_2\), where:

• \(x\): Norton’s starting cave.
• \(c_1\): Norton’s initial magnet pole (either N or S).
• \(y\): the treasure cave.
• \(c_2\): the magnet pole in cave \(y\) (either N or S).

It is guaranteed that \(1 \le n \le 50\) and \(q \ge 3\).

outputFormat

For each query, output a single line containing the expected number of time steps before Norton finds the treasure. Your answer should have an absolute or relative error of at most \(10^{-6}\).

sample

5 0.5
1 2
2 3
3 4
3 5
3
1 N 3 S
5 S 3 S
3 N 3 N

5.000000
4.000000
0.000000

</p>