Tree Kadane | cho.sh

$1$부터 $N$까지 번호가 매겨진 $N$개의 정점으로 이루어진 트리 $T$가 주어진다. 각 $i$번 정점은 정수 가중치 $A_i$를 가진다.

$T$의 연결 부분 집합 $S$는 $T$의 정점들의 공집합이 아닌 부분 집합으로, $S$에 속하는 두 정점 $a$, $b$에 대해 $S$에 속한 정점만을 사용하는 $a$에서 $b$로 가는 경로가 $T$에 존재한다.

다음 $Q$개의 쿼리를 처리해야 한다.

$k$ $x$: $A_k$를 $x$로 바꾸고 $T$의 연결 부분 집합 $S$에 대한 $\sum_{i\in S}{A_i}$의 최댓값을 출력한다.

첫 번째 줄에 정점의 개수를 나타내는 정수 $N$이 주어진다.

두 번째 줄에 각 정점의 가중치를 나타내는 $N$개의 정수 $A_1,A_2,\dots ,A_N$이 공백으로 구분되어 주어진다.

다음 $N-1$개의 줄 중 $i$번째 줄에 두 정수 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. 이들은 $i$번째 간선의 양 끝 점을 나타낸다.

다음 줄에 쿼리의 개수를 나타내는 정수 $Q$가 주어진다.

다음 $Q$개의 줄에 걸쳐 각 줄에 각 쿼리를 나타내는 두 정수 $k$와 $x$가 공백으로 구분되어 주어진다.

$Q$개의 줄에 걸쳐 쿼리의 정답을 한 줄에 하나씩 출력한다.