{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\u003cp\u003eGiven a tree with \u003cvar\u003en\u003c/var\u003e \u003cvar\u003e(1 ≤ n ≤ 200,000)\u003c/var\u003e nodes and a list of \u003cvar\u003eq\u003c/var\u003e \u003cvar\u003e(1 ≤ q ≤ 100,000)\u003c/var\u003e queries,\nprocess the queries in order and output a value for each output query.\nThe given tree is connected and each node on the tree has a weight \u003cvar\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003e(-10,000 ≤ w\u003csub\u003ei\u003c/sub\u003e ≤ 10,000)\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003eEach query consists of a number \u003cvar\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003e(t\u003csub\u003ei\u003c/sub\u003e \u003d 1, 2)\u003c/var\u003e, which indicates the type of the query , and three numbers \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003e(1 ≤ a\u003csub\u003ei\u003c/sub\u003e, b\u003csub\u003ei\u003c/sub\u003e ≤ n, -10,000 ≤ c\u003csub\u003ei\u003c/sub\u003e ≤ 10,000)\u003c/var\u003e.\nDepending on the query type, process one of the followings:\n\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cp\u003e (\u003cvar\u003et\u003csub\u003ei\u003c/sub\u003e \u003d 1\u003c/var\u003e: modification query)\nChange the weights of all nodes on the shortest path between \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (both inclusive) to \u003cvar\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e.\n\u003c/p\u003e\u003c/li\u003e\u003cli\u003e\u003cp\u003e (\u003cvar\u003et\u003csub\u003ei\u003c/sub\u003e \u003d 2\u003c/var\u003e: output query) \nFirst, create a list of weights on the shortest path between \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (both inclusive) in order. After that, output the maximum sum of a non-empty continuous subsequence of the weights on the list. \u003cvar\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e is ignored for output queries.\n\u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e\n\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe first line contains two integers \u003cvar\u003en\u003c/var\u003e and \u003cvar\u003eq\u003c/var\u003e.\n On the second line, there are \u003cvar\u003en\u003c/var\u003e integers which indicate \u003cvar\u003ew\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003ew\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e, ... , \u003cvar\u003ew\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003eEach of the following \u003cvar\u003en - 1\u003c/var\u003e lines consists of two integers \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ee\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003e(1 ≤ s\u003csub\u003ei\u003c/sub\u003e, e\u003csub\u003ei\u003c/sub\u003e ≤ n)\u003c/var\u003e,\nwhich means that there is an edge between \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ee\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e.\n\u003c/p\u003e\n\u003cp\u003e Finally the following \u003cvar\u003eq\u003c/var\u003e lines give the list of queries, each of which contains four integers in the format described above.\nQueries must be processed one by one from top to bottom.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003eFor each output query, output the maximum sum in one line.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e3 4\n1 2 3\n1 2\n2 3\n2 1 3 0\n1 2 2 -4\n2 1 3 0\n2 2 2 0\n\u003c/pre\u003e\n\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e6\n3\n-4\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e7 5\n-8 5 5 5 5 5 5\n1 2\n2 3\n1 4\n4 5\n1 6\n6 7\n2 3 7 0\n2 5 2 0\n2 4 3 0\n1 1 1 -1\n2 3 7 0\n\u003c/pre\u003e\n\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e12\n10\n10\n19\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e21 30\n10 0 -10 -8 5 -5 -4 -3 1 -2 8 -1 -7 2 7 6 -9 -6 3 4 9\n10 3\n3 2\n3 12\n12 4\n4 13\n4 9\n10 21\n21 1\n1 11\n11 14\n1 15\n10 6\n6 17\n6 16\n6 5\n5 18\n5 19\n10 7\n10 8\n8 20\n1 1 21 -10\n1 3 19 10\n2 1 13 0\n1 4 18 8\n1 5 17 -5\n2 16 7 0\n1 6 16 5\n1 7 15 4\n2 4 20 0\n1 8 14 3\n1 9 13 -1\n2 9 18 0\n1 10 12 2\n1 11 11 -8\n2 21 15 0\n1 12 10 1\n1 13 9 7\n2 6 14 0\n1 14 8 -2\n1 15 7 -7\n2 10 2 0\n1 16 6 -6\n1 17 5 9\n2 12 17 0\n1 18 4 6\n1 19 3 -3\n2 11 8 0\n1 20 2 -4\n1 21 1 -9\n2 5 19 0\n\u003c/pre\u003e\n\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e20\n9\n29\n27\n10\n12\n1\n18\n-2\n-3\n\u003c/pre\u003e\n"}}]}