{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N\u003cbr\u003e\u003cbr\u003e There are N - 1 edges numbered from 1 to N - 1.\u003cbr\u003e\u003cbr\u003e Each node has a value and each edge has a value. The initial value is 0.\u003cbr\u003e \u003cbr\u003e There are two kind of operation as follows:\u003cbr\u003e\u003cbr\u003e ● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.\u003cbr\u003e\u003cbr\u003e ● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.\u003cbr\u003e\u003cbr\u003e After finished M operation on the tree, please output the value of each node and edge.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The first line of the input is T (1 ≤ T ≤ 20), which stands for the number of test cases you need to solve.\u003cbr\u003e\u003cbr\u003e The first line of each case contains two integers N ,M (1 ≤ N, M ≤10\u003csup\u003e5\u003c/sup\u003e),denoting the number of nodes and operations, respectively.\u003cbr\u003e\u003cbr\u003e 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.\u003cbr\u003e\u003cbr\u003e For the next M line, contain instructions “ADD1 u v k” or “ADD2 u v k”. (1 ≤ u, v ≤ N, -10\u003csup\u003e5\u003c/sup\u003e ≤ k ≤ 10\u003csup\u003e5\u003c/sup\u003e)"}},{"title":"Output","value":{"format":"HTML","content":" For each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.\u003cbr\u003e\u003cbr\u003e The second line contains N integer which means the value of each node.\u003cbr\u003e\u003cbr\u003e The third line contains N - 1 integer which means the value of each edge according to the input order."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 2\r\n1 2\r\n2 3\r\n2 4\r\nADD1 1 4 1\r\nADD2 3 4 2\r\n4 2\r\n1 2\r\n2 3\r\n1 4\r\nADD1 1 4 5\r\nADD2 3 2 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n1 1 0 1\r\n0 2 2\r\nCase #2:\r\n5 0 0 5\r\n0 4 0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}