F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5349. -- 树

5349: 树

Time Limit: 35 Sec  Memory Limit: 256 MB
Submit: 20  Solved: 0
[Submit][Status][Discuss]

Description

给你一棵树,点带权,且以点1为根。有这么一个游戏:从根开始,每次拿出一个点,然后在它和它的所有儿子中
随机选择一个点(每个点的概率相同)。若这个点是当前拿出的点,游戏结束且你获得其点权的分数;否则拿出该点
,然后重复上述过程。
现在你要算出这个游戏的期望得分,而且要满足两个操作:
操作1:修改某个点的权值。
操作2:将某个节点为根的子树转移到另一个节点的下方。

Input

输入数据第一行包含一个数n,m,表示点的个数和操作个数。
第二行包含n个整数,表示每个点的点权。
接下来n行每行两个数,表示一条树边的两个端点。
在接下来m行每行3个数字type,x,y。表示一个操作。
若type=0,则表示将点x的权值修改成y;否则表示将x为根的子树转移到y下方。
(若y是x的后辈,则视为没有操作。)
n,m<=200000。

Output

对于每次操作,都输出操作过后进行游戏的期望得分。
注意:为了防止精度误差,这里将答案对10^9+7取模,并把除法看成是乘逆元。

Sample Input

5 3
2 3 3 4 4
1 2
1 3
2 4
2 5
0 3 1
1 2 3
1 5 3

Sample Output

222222226
166666670
416666672

HINT

Source

[Submit][Status][Discuss]

HOME Back