#P5349. 树

    ID: 4362 传统题 35000ms 256MiB 尝试: 22 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学贡献法数据结构Euler Tour Tree树算法子树转区间FHQ Treap 分裂合并维护顺序统计量标记复合数论模逆元逆元线性递推快速幂CF2600

树

树

题目描述

给定一棵以点 11 为根的树,每个点都有一个权值。

游戏从根开始。每一步,在当前点与它的所有儿子中等概率选择一个点:如果选中当前点,游戏结束,得分为当前点的权值;否则移动到选中的儿子,重复这个过程。

需要支持以下操作,并在每次操作后计算重新从根开始游戏的期望得分:

  • 修改某个点的权值。
  • 将以某个点为根的整棵子树移到另一个点下方,成为它的儿子。若目标点就是被移动子树的根,或是它的后代,则本次操作不生效。

输入格式

从标准输入读入。

第一行两个整数 n,mn,m,分别表示点数和操作数。

第二行 nn 个整数,表示各点的权值。

接下来 n−1n-1 行,每行两个整数,表示一条树边的两个端点。

接下来 mm 行,每行三个整数 type,x,ytype,x,y,表示一次操作:

  • 若 type=0type=0,将点 xx 的权值改为 yy。
  • 否则,将以点 xx 为根的子树移到点 yy 下方;若 yy 是 xx 的后代,则不执行移动。

输出格式

向标准输出对每次操作写出一行一个整数,表示操作后游戏的期望得分在模 109+710^9+7 意义下的值。分数中的除法按乘以模逆元计算。

样例

输入

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

数据范围

n,m≤200000n,m\le200000。