#2518. 查询子树

查询子树

Description

有一棵树,其节点用1,2,,n1, 2, …, n 标 记。开始时,第ii 个节点的权值为wiw_i 。有qq 个操作,操作分为两种类 型:①!! vv xx ,将节点vv 的权值修改为xx ;②?? vv dd ,查询到vv 距离不 超过dd 的所有节点的权值之和。节点uuvv 之间的距离是它们之间最短 路径上的边数。

Format

Input

包括几个测试用例。每个测试用例的第11行都包含nqn 、q 1nq105(1≤n ,q ≤10^5 );第22行都包含nn 个整数w1,w2,,wn0wn104w_ 1 , w_2 , …, w_n (0≤w_n≤10^4 );接下来的n1n -1行,每行都包含两个整数aia_ibib_i ,表示在aia_ibib_i 节点之间有一条边1aibin(1≤a_i ,b_i ≤n )。接下来是qq 行操作 1vn0x1040dn(1≤v ≤n ,0≤x ≤10^4 ,0≤d ≤n )

Output

对每个查询,都单行输出权值之和。

Samples

4 3
1 1 1 1
1 2
2 3
3 4
? 2 1
! 1 0
? 2 1
3 3
1 2 3
1 2
1 3
? 1 0
? 1 1
? 1 2
3
2
1
6
6

来源

HDU4918