![]() |
||||||||||
|
||||||||||
Query on the subtreeTime Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2631 Accepted Submission(s): 810 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
Sample Output
Author Xiaoxu Guo (ftiasch) Source | ||||||||||
|