연습문제

선물 나눠주기 (Hard)

난이도
Lv. 5
제출
52 명
참가자
19 명
정답률
3.70 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 15초 1024MB
Java 4초 1024MB
Python 15초 1024MB
C 1초 1024MB
C++ 1초 1024MB

이 문제는 선물 나눠주기 문제의 어려운 버전입니다. 두 버전의 유일한 차이점은 주어지는 질의의 정점에 대해 제한이 있는지 여부입니다.


산타는 도시 내에 있는 마을에 선물을 나눠주려고 합니다. 이 도시는 개의 마을로 이루어져 있고, 마을은 트리 모양을 이루고 있습니다. 트리를 이루고 있기에 이 도시는 개의 마을(노드)을 개의 간선이 연결하고 있는 모양이며 이로부터 모든 마을이 연결됩니다. Figure 1은 이 7인 경우의 예입니다.



처음 각 i번째 마을에는 정수 값이 주어져있습니다. 인 경우에는 해당 마을에 선물이 개 놓여 있음을, 인 경우에는 해당 마을에 선물이 개 만큼 배달이 되어야만 함을 의미합니다. 는 항상 0이며, 산타는 인 마을에 놓인 선물들을 잘 챙겨서 인 마을에 배달해야 합니다. Figure 2는 Figure 1에서 인 예입니다.



산타는 처음에 시작점에 해당하는 마을 를 잘 골라, 이 마을에서 출발하여 모든 선물 배달을 완료한 뒤 다시 시작 마을 로 되돌아오려고 합니다. 이때 선으로 연결된 두 마을을 지나는 데에는 1초가 소요되며, 전략을 잘 세워 선물 배달을 완료하고 다시 시작 위치로 돌아오는 데 걸리는 시간을 최소로 만들고자 합니다.


예로 Figure 2에서 만약 산타가 1번 마을에서 출발하여 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 순으로 이동했다면 모든 배달을 완료하고 다시 처음 위치로 돌아오게 되지만 이때 걸리는 시간은 총 6초가 됩니다. 하지만 만약 산타가 4번 마을에서 출발하여 4 -> 3 -> 2 -> 3 -> 4 순으로 이동했다면 모든 배달을 완료하고 다시 처음 위치로 돌아오는 시간이 총 4초가 되어 최소가 됩니다.


하지만 처음 주어진 들의 정보가 완벽한 정보는 아닐 수 있기에 산타는 여러 상황에 대해 최소 이동 시간을 추가로 구해보려고 합니다. 이는 개의 질의로 표현되며, 산타는 처음 주어진 에 대한 답을 구한 뒤 개의 질의를 순차적으로 실행한 이후의 결과를 매 질의마다 구해주려고 합니다. 즉, 번 답을 구해보려고 합니다.


질의는 형태로 주어지며, 이는 값에 를 더하고 값에 를 빼야함을 의미합니다.


만약 Figure 2에서 라는 질의가 주어졌다면, 도시는 Figure 3과 같은 모습으로 바뀌게 됩니다.



이 경우에는 산타가 5번 마을에서 출발하여 5 -> 4 -> 3 -> 2 -> 3 -> 6 -> 3 -> 4 -> 5순으로 이동하는게 8초로 최소가 됩니다.

이후 Figure 3에서 라는 질의가 주어졌다면, 도시는 Figure 4와 같은 모습으로 바뀌게 됩니다.



이 경우에는 산타가 1번 마을에서 출발하여 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 6 -> 7 -> 6 -> 3 -> 2 -> 1순으로 이동하는게 12초로 최소가 됩니다.


이후 Figure 4에서 라는 질의가 주어졌다면, 도시는 Figure 5와 같은 모습으로 바뀌게 됩니다.



이 경우에는 산타가 5번 마을에서 출발하여 5 -> 4 -> 3 -> 2 -> 3 -> 6 -> 7 -> 6 -> 3 -> 4 -> 5순으로 이동하는게 10초로 최소가 됩니다.

산타가 총 개의 상황에 대해 선물 배달을 완료하는데 걸리는 최소 시간을 구하는 프로그램을 작성해보세요.


본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

[조건 1] 4 ≤ ≤ 100,000

[조건 2] 1 ≤ ≤ 100,000

[조건 3]

[조건 4] ,

[조건 5] 1 ≤ ,

[조건 6] 1 ≤

입력형식

첫 번째 줄에는 마을의 수 이 주어집니다.

두 번째 줄에는 에 대한 정보 개가 공백을 사이에 두고 주어집니다. 부터 순서대로 까지 주어지며, 모든 가 0으로 주어지지는 않습니다. 는 항상 0임을 가정해도 좋습니다.

세 번째 줄부터는 개의 줄에 걸쳐 선의 정보 가 공백을 사이에 두고 주어집니다. 이는 번 마을과 번 마을이 선으로 직접 연결되어 있음을 뜻합니다.

번째 줄에는 질의의 수 가 주어집니다.

번째 줄부터는 개의 줄에 걸쳐 질의에 해당하는 정보 가 공백을 사이에 두고 주어집니다. 이는 값에 를 더하고 값에 를 빼야함을 의미합니다.

출력형식

개의 줄에 걸쳐 각 상황에 대해 산타가 선물 배달을 완료하는데 걸리는 최소 시간을 한 줄에 하나씩 출력합니다. 초기 상태부터 시작하여 각 질의가 순차적으로 실행된 직후의 상황에서의 답을 출력합니다. 만약 놓여 있는 선물이 전혀 없는 경우라면 을 출력합니다.

입력예제1

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

출력예제1

4 8 12 10

입력예제2

5 1 0 0 0 -1 1 2 2 3 3 4 4 5 3 5 1 1 3 2 3 2 4 4

출력예제2

8 0 2 4