

Query on the subtreeTime Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2604 Accepted Submission(s): 806 Problem Description bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n. At the very begining, the ith vertex is assigned with weight w_{i}. 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≤10^{5}). The second line contains n integers w_{1},w_{2},…,w_{n} (0≤w_{i}≤10^{4}). Each of the following (n  1) lines contain 2 integers a_{i},b_{i} denoting an edge between vertices a_{i} and b_{i} (1≤a_{i},b_{i}≤n). Each of the following q lines contain the operations (1≤v≤n,0≤x≤10^{4},0≤d≤n). Output For each tests: For each queries, a single number denotes the total weight. Sample Input
Sample Output
Author Xiaoxu Guo (ftiasch) Source  
