페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3609

트리와 쿼리 4 5s 512MB

문제

노드가 N개 있고, 노드에 가중치가 부여된 트리가 있다. 나올 수 있는 쿼리는 다음과 같다.

쿼리 1: A번 노드의 가중치를 X만큼 증가시킨 뒤, 전체 트리에서 가능한 연결 요소 중 가중치 합의 최댓값을 출력한다. 크기가 0인 연결 요소도 가능하며, 이 경우 가중치 합은 0이다.

위 쿼리를 빠르게 수행하는 프로그램을 작성하여라.​ 


입력

첫 번째 줄에는 노드의 수 N (2 ≤ N ≤ 300,000)가 주어진다. 

두 번째 줄에는 정점의 가중치 V_i (-10^9 ≤ V_i ≤ 10^9)가 N개 주어진다. 

세 번째 줄부터 N-1개의 줄에는 트리의 각 간선이 연결하는 두 정점의 번호가 주어진다. 

N+1번째 줄에는 쿼리의 수 Q (1 ≤ Q ≤ 300,000)가 주어진다. 

N+2번째 줄부터 Q개의 줄에는 쿼리가 주어진다. 쿼리 1은 A X로 주어진다. (1 ≤ A ≤ N,\ 0 < X ≤ 10^9)


출력

쿼리 1의 정답을 한 줄에 하나씩 출력한다. 


예제 

5

2 -10 3 -3 2

1 2

2 3

3 4

2 5

4

2 8

2 1

4 1

4 10
5

6

6

14

로그인해야 코드를 작성할 수 있어요.