题目背景

浏览～

题目描述

众所周知，MloVtry有很多纸片人老婆（我永远喜欢IA.jpg），不过很可惜，并不是所有人都是死宅，所以很多人无法理解MloVtry 的兴趣。

Vittorio就是一个坏文明，他十分喜欢刁难MloVtry。

现在Vittorio构建了一个n个点的地图，MloVtry必须穿过这张图才能prpr到它的纸片人老婆。但是穿过地图听起来就太费力气了，于是MloVtry就咬住1号点狠狠一抖，把这张图甩成了一颗有根树。

MloVtry是个好文明，它有一个高科技的设备---弹力装置---来帮助自己。具体的，如果MloVtry在i号点，这个装置会把它从当前点向下弹出a[i]（这个值被称为弹力值）个距离---我们认为1号点是在上方的，并且每条边的距离是1。不过问题是MloVtry并不能准确控制自己的落点，换言之降落在哪个位置是不确定的，但是MloVtry可以肯定的是降落的点一定可以让它不拐弯的走回出发的点（也就是只能落在子树内）---它一向认为自己是头耿直的生物。当然，由于a[i]是个正整数，所以它一定可以跳到它老婆的身旁。

现在MloVtry有几个问题，它想知道假设它从x号点出发，赶到老婆身边的期望步数是多少，不过由于化图为树这个操作太耗费能量了，所以这个问题就只能交给它最好的好朋友---您这头神犇了。

但是之前说过，Vittorio是个坏文明，他对弹力装置做了些手脚，每个弹力装置只有在没有树内的落点时才会跳出。并且他可能会偷偷更换掉一些节点上的弹力装置，这可能会带来一点难度，不过您一定没问题。

输入格式

第1行两个整数n,q，表示这个图有n个节点，并且接下来有q个操作。

第2行是一行整数，表示a[i]数组的初始值。

接下来n-1行，每行两个整数u，v，表示有一条连接u，v的无向边。

接下来q行，每行有3~2个整数，具体的：

1 x y 表示Vittorio将x号节点上的弹力装置换成了一个弹力值为y的弹力装置。

0 x 表示MloVtry想知道从x号节点出发的期望步数是多少。

输出格式

请对每个询问输出一个分数

特别的，如果分母为1也请把它输出出来

（如：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

提示

样例解释

第一个询问

1-2-4-5-out

1-2-5-out

1-8-out

1-3-6-10-out

1-3-7-out

总路径数为:5

总跳跃次数为:16

1-4-9-out

1-5-out

1-6-10-out

1-7-out

（由于存在树内的落点，所以1-out无法行走）

总路径数为:4

总跳跃次数为:10

n<=100000 ,q<=200000

不对a[i]的值做出保证

对于30%的数据，有n<=1000

对于50%的数据，有n<=10000

特殊的

对于20%的数据，有a[i]=1

保证最后答案在2147483647的范围之内。

数据保证在window环境下随机生成。