![]() |
||||||||||
|
||||||||||
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 | ||||||||||
|