Tree Kadane

시간 제한3초메모리 제한1024 MB

요약

가중치가 있는 트리에서 정점 하나의 가중치를 바꾸는 갱신이 주어질 때마다, 공집합이 아닌 연결 부분 집합의 합의 최댓값을 출력한다.

문제

$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$ 개의 줄에 걸쳐 쿼리의 정답을 한 줄에 하나씩 출력한다.

예제 1

입력

5
3 -1 -4 -1 -5
1 2
1 3
3 4
3 5
5
1 -2
3 2
4 1
2 5
1 -9

예상 출력