破云来
题号：NC247432
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵树，根为1，每个点有点权。现在进行如下操作：从所有的点中以正比于的概率选择一个节点u，重复k次（k次独立，选的点可以重复）。

形式化的，每一次选择点u的概率为，独立重复k次，设这k次选出的点分别为，记，你希望知道L的期望值。

此外，你还会进行m次修改操作，每一次修改会选择某个点u并修改的值。在每次修改后，你都希望知道L的期望值，模输出。

输入描述:

第一行n,m,k，代表树的节点个数，修改次数和每次取的节点个数。
接下来一行n个数字，代表初始的
接下来n - 1行，每行两个数字u,v，代表树上的一条边，保证给出的是一棵合法的树。
再接下来m行，每行两个数字，代表将节点u的权值修改为
保证任意时刻

输出描述:

行，分别代表初始的L的期望值和每次修改后L的期望值，模输出
示例1

输入

复制 
4 3 1
1 1 1 1
1 2
1 3
2 4
1 2
2 4
2 3

输出

复制 
500000006
400000005
125000003
142857146
示例2

输入

复制 
5 4 2
1 3 4 2 5
1 2
2 3
1 4
3 5
3 6
2 4
1 6
5 2

输出

复制 
595555562
574394470
592592599
241965977
490000005