P4842 City Travel.

Country W is vast and rich. It consists of $n$ cities, connected by $n-1$ bidirectional roads, each road connecting two cities. Any two cities can reach each other. The beautiful scenery of Country W attracts many tourists. Based on the tourists' ratings for each city, we define the beauty of city $i$ as $a_i$. For a trip from city $x$ to city $y$, the happiness index gained is the sum of the beauties of all cities on the path from city $x$ to city $y$ (including $x$ and $y$). We define this value as $H(x,y)$. Now, Xiao A is in city $X$ and Sharon is in city $Y$. They want to know: if we choose any two cities $x$ and $y$ (where $x$ may equal $y$) among all cities on the path from city $X$ to city $Y$, what is the expected value of $H(x,y)$? We denote this expected value as $E(x,y)$. Of course, the traffic conditions between cities are unpredictable, so we cannot rule out that at some moments some roads become impassable. At some moments, new roads may be added. Also, as tourists' tastes change, the beauty of some cities may change as well. As Mr. T, who is responsible for the tourism industry in Country W, requires you to write a program to simulate all the processes above.

The first line contains two integers $n,m$, representing the number of cities and the number of operations. The next line contains $n$ integers, where the $i$-th integer represents $a_i$. The next $n-1$ lines each contain two integers $u,v$, indicating there is a road between $u$ and $v$. The next $m$ lines describe the following operations: - `1 u v` If there is no road directly connecting cities $u$ and $v$, ignore this operation; otherwise, delete the road between $u$ and $v$. - `2 u v` If cities $u$ and $v$ are connected, ignore this operation; otherwise, add a road between $u$ and $v$. - `3 u v d` If cities $u$ and $v$ are not connected, ignore this operation; otherwise, increase the beauty of all cities on the path from city $u$ to city $v$ (including $u$ and $v$) by $d$. - `4 u v` Query the value of $E(u,v)$.

For operation 4, output the answer as a reduced fraction $\frac{p}{q}$. If $u$ and $v$ are not connected, output `-1`.

For all testdata, $1\le N\le 50000,1\le M\le 50000,1\le a_i\le 10^6,1\le D\le 100,1\le u,v\le N$. Translated by ChatGPT 5