세그먼트 트리를 써 보세요

시간 제한2초메모리 제한512 MB

요약

가중치가 있는 트리에서 경로의 모든 가중치를 같은 값으로 바꾸는 갱신과, 경로 위 가중치 열의 비어 있지 않은 최대 연속 부분합을 구하는 질의를 처리한다. n은 200,000, q는 100,000까지 주어진다.

난이도: 어려움10점 중 9점
유형: 세그먼트 트리, 트리, DFS, 분할 정복
정답자: 아직 제출이 없습니다

문제

n (1 ≤ n ≤ 200,000)개의 노드로 이루어진 트리와 q (1 ≤ q ≤ 100,000)개의 쿼리가 주어진다. 쿼리를 순서대로 처리하면서 각 출력 쿼리마다 값을 하나씩 출력한다. 트리는 연결되어 있고, 각 노드에는 가중치 wi (-10,000 ≤ wi ≤ 10,000)가 있다.

각 쿼리는 쿼리의 종류를 나타내는 수 ti (ti = 1, 2)와 세 수 ai, bi, ci (1 ≤ ai, bi ≤ n, -10,000 ≤ ci ≤ 10,000)로 이루어진다. 쿼리의 종류에 따라 다음 중 하나를 처리한다.

(ti = 1: 변경 쿼리) ai와 bi 사이의 최단 경로에 있는 모든 노드(양 끝 포함)의 가중치를 ci로 바꾼다.
(ti = 2: 출력 쿼리) 먼저 ai와 bi 사이의 최단 경로에 있는 노드(양 끝 포함)의 가중치를 순서대로 나열한 리스트를 만든다. 그다음 리스트에서 비어 있지 않은 연속 부분 수열의 합의 최댓값을 출력한다. 출력 쿼리에서 ci는 무시한다.

입력

첫째 줄에 두 정수 n과 q가 주어진다. 둘째 줄에 w1, w2, ..., wn을 나타내는 n개의 정수가 주어진다.

이어지는 n - 1개의 줄에는 두 정수 si와 ei (1 ≤ si, ei ≤ n)가 주어지며, 이는 si와 ei 사이에 간선이 있음을 뜻한다.

마지막으로 q개의 줄에 위에서 설명한 형식의 정수 네 개로 이루어진 쿼리 목록이 주어진다. 쿼리는 위에서 아래로 하나씩 처리해야 한다.

출력

각 출력 쿼리마다 최대 합을 한 줄에 출력한다.

예제3

예제 1

입력

예상 출력

6
3
-4

예제 2

입력

7 5
-8 5 5 5 5 5 5
1 2
2 3
1 4
4 5
1 6
6 7
2 3 7 0
2 5 2 0
2 4 3 0
1 1 1 -1
2 3 7 0

예상 출력

예제 3

입력

21 30
10 0 -10 -8 5 -5 -4 -3 1 -2 8 -1 -7 2 7 6 -9 -6 3 4 9
10 3
3 2
3 12
12 4
4 13
4 9
10 21
21 1
1 11
11 14
1 15
10 6
6 17
6 16
6 5
5 18
5 19
10 7
10 8
8 20
1 1 21 -10
1 3 19 10
2 1 13 0
1 4 18 8
1 5 17 -5
2 16 7 0
1 6 16 5
1 7 15 4
2 4 20 0
1 8 14 3
1 9 13 -1
2 9 18 0
1 10 12 2
1 11 11 -8
2 21 15 0
1 12 10 1
1 13 9 7
2 6 14 0
1 14 8 -2
1 15 7 -7
2 10 2 0
1 16 6 -6
1 17 5 9
2 12 17 0
1 18 4 6
1 19 3 -3
2 11 8 0
1 20 2 -4
1 21 1 -9
2 5 19 0

예상 출력