MloVtry与jump

浏览～

众所周知，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环境下随机生成。