#P5349. 树
树
树
题目描述
给定一棵以点 为根的树,每个点都有一个权值。
游戏从根开始。每一步,在当前点与它的所有儿子中等概率选择一个点:如果选中当前点,游戏结束,得分为当前点的权值;否则移动到选中的儿子,重复这个过程。
需要支持以下操作,并在每次操作后计算重新从根开始游戏的期望得分:
- 修改某个点的权值。
- 将以某个点为根的整棵子树移到另一个点下方,成为它的儿子。若目标点就是被移动子树的根,或是它的后代,则本次操作不生效。
输入格式
从标准输入读入。
第一行两个整数 ,分别表示点数和操作数。
第二行 个整数,表示各点的权值。
接下来 行,每行两个整数,表示一条树边的两个端点。
接下来 行,每行三个整数 ,表示一次操作:
- 若 ,将点 的权值改为 。
- 否则,将以点 为根的子树移到点 下方;若 是 的后代,则不执行移动。
输出格式
向标准输出对每次操作写出一行一个整数,表示操作后游戏的期望得分在模 意义下的值。分数中的除法按乘以模逆元计算。
样例
输入
5 3
2 3 3 4 4
1 2
1 3
2 4
2 5
0 3 1
1 2 3
1 5 3
输出
222222226
166666670
416666672
数据范围
。