Problem Description
bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n. At the very begining, the i-th vertex is assigned with weight wi.
There are q operations. Each operations are of the following 2 types:
Change the weight of vertex v into x (denoted as "! v x"),
Ask the total weight of vertices whose distance are no more than d away from vertex v (denoted as "? v d").
Note that the distance between vertex u and v is the number of edges on the shortest path between them.
Input
The input consists of several tests. For each tests:
The first line contains n,q (1≤n,q≤105). The second line contains n integers w1,w2,…,wn (0≤wi≤104). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following q lines contain the operations (1≤v≤n,0≤x≤104,0≤d≤n).
Output
For each tests:
For each queries, a single number denotes the total weight.
Sample Input
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
Sample Output
3
2
1
6
6