연습문제
선물 나눠주기 (Hard)
- 난이도
- Lv. 5
- 제출
- 52 명
- 참가자
- 19 명
- 정답률
- 3.70 %
- 지원 언어
-
CC++JavaPythonJavaScript
로그인 후 문제풀이가 가능합니다.
언어별 시간/메모리
언어 | 시간 | 메모리 |
---|---|---|
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