Description

Given a tree-shaped circuit, each edge in the tree has a resistor $R_i$, and all resistances are $10000\ Ω$. The figure below shows a tree-shaped circuit with $4$ nodes:

All leaf nodes in the tree (nodes of degree $1$ are called leaves) are connected to ground, each line is connected to ground, and each line carries a $10000\ Ω$ resistor, forming the network shown below:

There are two types of operations:

C u v w: Insert a voltage source in series on edge $(u, v)$, with magnitude $w$ volts. The source is placed on the side closer to node $u$ (as shown below), with its negative terminal pointing toward $u$. Note that multiple voltage sources can be inserted in series on the same edge.

Q u: Query the current voltage of node $u$, measured with respect to ground.

After performing C 2 4 5 on the figure above, the network becomes:

At this time, the voltage at each node is as labeled in the figure.

Input Format

The input file circuit.in contains two integers $N, M$ on the first line, representing the number of nodes in the tree and the number of operations, respectively. The next $N-1$ lines each contain two integers $u, v$, indicating that there is an edge connecting nodes $u$ and $v$, and this edge contains exactly one resistor.

Then there are $M$ lines, each containing one command in the format described above.

Output Format

Output to circuit.out. For each Q command, output a single number representing the voltage at that node at that moment. You may print any number of decimal places; your answer is considered correct if it differs from the standard answer by at most $10^{-3}$.

4 3
1 2
2 3
2 4
Q 2
C 2 4 5
Q 2

0.0000000000
-1.6666666666

Hint

[Sample Explanation]

For the first query, since there is no voltage source in the original circuit, there is no current, and all node voltages are equal (otherwise, if there exists $U_i > U_j$, there would be current flowing from $i$ to $j$, contradicting the absence of a source). They are all equal to the ground potential $0\text{V}$.

After adding a $5\text{V}$ voltage source on $(2, 4)$, the new circuit is as shown in the problem statement.

After simplification, the new circuit can be seen as series (source, $R_2+10000$, parallel ($R_1+10000$, $R_3+10000$)), hence the equivalent resistance is:

$$R 2 +10000+\frac{1}{\frac{1}{R_3 +10000}+\frac{1}{R_1 +10000}}=30000\ Ω$$

Therefore, the current flowing through node $4$ is $\frac{5}{30000}\ A$, so $U_4=\frac{5}{3}V$ and $U_2=U_4+R_2\cdot I-5=-\frac{5}{3}V$; since $U_1$ and $U_3$ are symmetric, by the voltage division relation we have $U_1 =U_3 =U_2\times\frac{10000}{10000+10000}=-\frac{5}{6}V$.

[Constraints]

$30\%$ of the testdata guarantees $N, M ≤ 30$.

$60\%$ of the testdata guarantees $N, M ≤ 3000$.

$100\%$ of the testdata guarantees $3 ≤ N, M ≤ 50000$, $1 ≤ u, v ≤ n$, $1 ≤ w ≤ 10$, and the length of the longest chain in the tree does not exceed $50$.

Translated by ChatGPT 5