|
||||||||||
Query on the subtreeTime Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2629 Accepted Submission(s): 809 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 | ||||||||||
|