Virus Infection Simulation on Tree Networks

This problem simulates the propagation of a virus with multiple variants in a closed local area network (LAN) consisting of n computers connected by cables forming a tree structure. Initially, each computer i (for i from 1 to n) is infected by a unique virus variant. A special computer called the core computer is used as a reference point (initially computer 1).

There are m operations in the experiment. Each operation is one of the following three types:

• RELEASE x: A new virus variant (which did not exist before) is released on computer x. Immediately after release the virus starts propagating along the unique shortest path (in the tree) from x to the core computer. The propagation behavior is as follows: when the new variant infects a computer that is infected by some old variant, it will destroy the old variant completely and take over the computer. However, if along the propagation the new variant has not yet destroyed a particular old variant type, then upon encountering a computer infected with that variant the new virus must spend an extra 1 unit time to analyze (and then destroy) that variant. If the new variant has already destroyed that variant type earlier along the path, then it can destroy it instantly. In other words, the time it takes to infect the computers on the path equals the number of distinct virus variants (from the already infected computers) encountered on the path after the starting computer.
• RECENTER x: The core computer is changed from its current value to computer x. In addition, after recentering, the virus on the previous core computer produces a new variant and immediately infects along the unique shortest path from the old core to the new core (following the same propagation rules as in RELEASE). That is, a RECENTER x is equivalent to first changing the core computer to x and then performing a RELEASE y operation where y is the old core computer.
• REQUEST x: For this query, consider the key set of computer x. A computer y is in the key set of x if and only if the unique shortest path from y to the current core computer passes through x. The query asks: if we were to release a new virus variant on every computer in the key set of x (independently), what would be the average infection time? Here the infection time for a release on computer y is defined as the number of distinct virus variants encountered on the path from y to the core computer (excluding the starting computer y itself). Note that even computer x is considered (since its own path to the core includes x).

Your task is to simulate the experiment and answer all REQUEST queries. If a new virus is released at a computer, update the infection status of all computers along the propagation path to this new variant. New virus variants are assigned unique IDs sequentially (starting from n+1 for the first new variant release).

The propagation between two computers is assumed to be instantaneous; only the extra time for analyzing a type (once per distinct old variant along the path) is counted.

Note on paths: Since the LAN forms a tree, the unique shortest path between any two computers can be found. When the core computer changes, the tree is effectively re-rooted at the new core, and the key set of a computer x is then the subtree of x in this re-rooted tree.

inputFormat

The first line contains two integers n and m separated by a space, where n is the number of computers and m is the number of operations.

The next n−1 lines each contain two integers u and v, representing an undirected cable connection between computers u and v.

The following m lines each contain an operation in one of the following formats:

• RELEASE x
• RECENTER x
• REQUEST x

It is guaranteed that the given connections form a tree. Initially, the core computer is 1, and each computer i is infected with a unique virus variant labeled i.

outputFormat

For each REQUEST operation, output a line containing the average infection time (a floating‐point number) with exactly 6 decimal places.

sample

3 5
1 2
1 3
REQUEST 1
RELEASE 2
REQUEST 1
RECENTER 3
REQUEST 1

0.666667
0.666667
1.000000