Dynamic Tree Expected Path Sum

W Country has n cities connected by n-1 bidirectional roads forming a tree (i.e. there is a unique path between any pair of cities). Each city i has a beauty value \(a_i\). For a travel between two cities x and y, the joy index is defined as the sum of the beauties of all cities on the unique simple path connecting x and y (including both endpoints), denoted by \(H(x,y)\).

Now, given two distinguished cities X and Y (where A is at city X and Sharon is at city Y), one is asked to choose two cities \(x\) and \(y\) from the unique path between X and Y (it is allowed that \(x = y\)). The expected joy index \(E(x,y)\) is defined as the average of \(H(x,y)\) over all choices of \(x\) and \(y\). Formally, if the path from X to Y includes \(k\) cities, then there are \(\frac{k(k+1)}2\) pairs (with order of the cities along the path preserved) and

[ E(x,y) = \frac{1}{\frac{k(k+1)}2} \sum_{1 \le i \le j \le k} \left( \sum_{t=i}^{j} a_{t} \right). ]

In addition, the connectivity of the cities dynamically changes: at some moments some roads become unavailable, while at other moments new roads are added; also, the beauty value of a city may change over time.

You are to process a sequence of operations. The operations are described below:

• Q X Y: Query the expected value \(E(x,y)\) along the unique simple path between city X and city Y in the current graph. It is guaranteed that X and Y are connected.
• U X v: Update the beauty of city X to v.
• R u v: Remove (block) the road between cities u and v.
• A u v: Add a new road between cities u and v.

Input constraints: The initial graph consists of n cities and n-1 roads (hence a tree), but after road removals and additions the graph remains such that for any query the two specified cities are connected by a unique simple path. You may assume the number of cities and operations are small so that a solution with moderate time complexity is acceptable.

inputFormat

The first line contains two integers n and q, the number of cities and the number of operations.

The second line contains n integers, where the i-th integer denotes \(a_i\), the beauty of the i-th city.

The next n-1 lines each contain two integers u and v, indicating that there is a bidirectional road connecting cities u and v.

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

• Q X Y: Query the expected value on the path between cities X and Y.
• U X v: Update the beauty of city X to v.
• R u v: Remove the road between cities u and v.
• A u v: Add a new road between cities u and v.

It is guaranteed that for every query operation, the two cities are connected by a unique simple path.

outputFormat

For each query operation Q, output a line containing the expected value \(E(x,y)\) on the corresponding path. The answer should be a floating‐point number rounded to 6 decimal places.

sample

5 7
3 1 4 1 5
1 2
2 3
3 4
4 5
Q 1 5
U 3 10
Q 1 5
R 3 4
Q 1 3
A 3 4
Q 2 5

6.133333
9.733333
7.166667
9.000000

</p>