트리 카데인

시간 제한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$ 가 공백으로 구분되어 주어진다.

각 쿼리의 답을 주어진 순서대로 한 줄에 하나씩 출력한다.

예제 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

예상 출력