MloVtry's Elastic Journey

MloVtry is on a quest to reach his beloved paper-wife. His map, originally a graph with n nodes, has been transformed into a rooted tree with node 1 at the top. Each node i is equipped with an elastic device having a bounce value a[i]. When MloVtry is at node i, the device attempts to bounce him exactly a[i] edges downward. In other words, he will land at a node j in the subtree of i such that the distance from i to j is exactly a[i]. However, if no such node exists in the subtree, the device does not bounce, meaning that MloVtry has reached his destination (i.e. his paper-wife is right there).

Note that since a[i] is always a positive integer, if a bounce occurs the landing node is always in the subtree of i along a straight downward path (i.e. without switching branches). In every bounce the outcome is uniformly random among all valid landing nodes.

The expected number of bounces starting from a node x is defined recursively. Let \(S(i) = \{ j \in \text{subtree}(i) : \text{dist}(i,j)=a[i] \}\). Then the expected steps from node i are:

[ E(i) = \begin{cases} 0, & \text{if } S(i)=\emptyset,\ 1 + \frac{1}{|S(i)|}\sum_{j\in S(i)}E(j), & \text{otherwise.} \end{cases} ]

You are given the tree and an initial array of bounce values. Then, you will be given q queries. A query is one of the following types:

• Q x: Report the expected number of bounces needed if MloVtry starts from node x.
• U x y: Update the bounce value at node x to y.

Your task is to answer all query of type Q correctly.

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 2000), representing the number of nodes and the number of queries.

The second line contains n positive integers: a[1], a[2], …, a[n], where a[i] is the bounce value at node i.

Each of the next n − 1 lines contains two integers u and v indicating that there is an edge between nodes u and v. The tree is rooted at node 1.

Each of the following q lines contains a query in one of the following two formats:

• Q x: Query the expected number of bounces starting from node x.
• U x y: Update the bounce value at node x to y (a positive integer).

outputFormat

For each query of the form Q x, output a line containing the expected number of bounces starting from node x. Print the answer as a floating‐point number with at least 6 digits after the decimal point.

sample

5 3
2 1 1 1 1
1 2
1 3
2 4
2 5
Q 1
U 2 2
Q 1

1.000000
1.000000

</p>