![]() |
||||||||||
|
||||||||||
TreeTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 6974 Accepted Submission(s): 1244 Problem Description You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N There are N - 1 edges numbered from 1 to N - 1. Each node has a value and each edge has a value. The initial value is 0. There are two kind of operation as follows: ¡ñ ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k. ¡ñ ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k. After finished M operation on the tree, please output the value of each node and edge. Input The first line of the input is T (1 ¡Ü T ¡Ü 20), which stands for the number of test cases you need to solve. The first line of each case contains two integers N ,M (1 ¡Ü N, M ¡Ü105),denoting the number of nodes and operations, respectively. The next N - 1 lines, each lines contains two integers u, v(1 ¡Ü u, v ¡Ü N ), denote there is an edge between u,v and its initial value is 0. For the next M line, contain instructions ¡°ADD1 u v k¡± or ¡°ADD2 u v k¡±. (1 ¡Ü u, v ¡Ü N, -105 ¡Ü k ¡Ü 105) Output For each test case, print a line ¡°Case #t:¡±(without quotes, t means the index of the test case) at the beginning. The second line contains N integer which means the value of each node. The third line contains N - 1 integer which means the value of each edge according to the input order. Sample Input
Sample Output
Source | ||||||||||
|