Description

As we all know, MloVtry has many 2D waifus (I will always love IA.jpg). Unfortunately, not everyone is an otaku, so many people cannot understand MloVtry’s interests.

Vittorio is a “bad civilization” who loves to make things hard for MloVtry.

Now Vittorio has built a map with $n$ nodes. MloVtry must traverse this map to prpr his 2D waifu. But traversing the map sounds too tiring, so MloVtry bites node $1$ and shakes hard, turning the map into a rooted tree with node $1$ at the top.

MloVtry is a “good civilization” and has a high-tech device — a bounce device — to help. Specifically, if MloVtry is at node $i$, the device will bounce him downward by distance $a[i]$ (this value is called the bounce value). We consider node $1$ to be the root (on top), and each edge has length $1$. However, MloVtry cannot accurately control the landing point; in other words, where he lands is uncertain. What he can be sure of is that the landing node must allow him to walk straight back to the starting node without turning (that is, he can only land within the subtree of $i$). Since $a[i]$ is a positive integer, he will definitely be able to jump to his waifu’s side.

MloVtry has a few questions: he wants to know, if he starts from node $x$, what is the expected number of steps to reach his waifu. Each jump counts as one step, and when there is more than one valid landing node inside the subtree of the current node at exact distance $a[i]$, the device chooses one uniformly at random. If there is no such node inside the tree, the jump goes “out”, and the process ends. Since transforming the graph into a tree consumes too much energy, this task can only be handed to his best friend — you.

But as mentioned earlier, Vittorio is a “bad civilization”. He has tampered with the bounce devices: a bounce device only jumps “out” when there is no landing node inside the tree. He may also secretly replace the bounce device at some nodes, which may add a bit of difficulty, but you will be fine.

Input Format

• The first line contains two integers $n, q$, meaning the graph has $n$ nodes and there are $q$ operations.
• The second line contains $n$ integers, the initial values of the array $a[i]$.
• The next $n - 1$ lines each contain two integers $u, v$, indicating an undirected edge between $u$ and $v$.
• The next $q$ lines each describe one operation, in one of the following formats:
  • 1 x y: Vittorio replaces the bounce device at node $x$ with a new one whose bounce value is $y$, i.e., set $a[x] = y$.
  • 0 x: MloVtry asks for the expected number of steps starting from node $x$.

Output Format

For each query, output a fraction.

In particular, even if the denominator is $1$, you should still output it. For example: 2/1.

10 3
1 1 1 1 1 1 1 1 1 1
1 2
1 8
1 3
3 6
3 7
6 10
2 4
2 5
4 9
0 1
1 1 2
0 1

16/5
5/2

Hint

Sample explanation.

First query.

1-2-4-5-out.

1-2-5-out.

1-8-out.

1-3-6-10-out.

1-3-7-out.

Total number of paths: 5.

Total number of jumps: 16.

Second query.

1-4-9-out.

1-5-out.

1-6-10-out.

1-7-out.

(Since there exist landing nodes inside the tree, 1-out cannot occur.)

Total number of paths: 4.

Total number of jumps: 10.

Constraints

• $n \le 100000$, $q \le 200000$.
• No bounds are guaranteed for $a[i]$.
• For 30% of the testdata, $n \le 1000$.
• For 50% of the testdata, $n \le 10000$.
• Special: For 20% of the testdata, $a[i] = 1$.
• It is guaranteed that the final answer is within the range of $2147483647$.
• The testdata is randomly generated under the Windows environment.

Translated by ChatGPT 5