{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eДано дерево состоящий из \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e вершин, пронумерованных от \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e до \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, каждая вершина содержит начальное значение \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. \u003cp\u003eДерево поддерживает два типа запросов:\u003c/p\u003e\u003cul\u003e \u003cli\u003e «\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e» — вывести максимальную сумму подотрезка которая находиться на пути от \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e до \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e; \u003c/li\u003e\u003cli\u003e «\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e» — присвоить значение \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e ко всем вершинам которые находятся на пути от \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e до \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eВ первой строке содержится целое число \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100000)\u003c/span\u003e. Во второй строке содержится \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e целых чисел \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, ..., \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(-10000 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10000)\u003c/span\u003e. В каждой из следующих \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e–1\u003c/span\u003e строк содержится по два целых числа, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e и \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e)\u003c/span\u003e, означающих, что существует ребро между вершинами \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e и \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003cp\u003eВ следующей строке содержится целое число \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 100000)\u003c/span\u003e\u003c/p\u003e\u003cp\u003eКаждая из следующих \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e строк содержит запрос в описанном выше формате. Гарантируется, что для всех запросов выполняется: \u003cspan class\u003d\"tex-span\"\u003e1≤ \u003ci\u003eu, v\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, -10000 ≤ \u003ci\u003ec\u003c/i\u003e ≤ 10000\u003c/span\u003e.\u003c/p\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eДля каждого запроса первого типа надо вывести ответ на запрос на отдельной строке. Ответы на запросы выводите в порядке следования запросов во входных данных.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cpre\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\n5\n-3 -2 1 2 3\n1 2\n2 3\n1 4\n4 5\n3\n1 2 5\n2 3 4 2\n1 2 5\n\n\u003cstrong\u003eOutput:\u003c/strong\u003e\n5\n9\u003cbr /\u003e\u003cbr /\u003e\u003c/pre\u003e"}}]}