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

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

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

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

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

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

질의는 $(x_i,y_i,z_i)$형태로 주어지며, 이는 $a_{x_i}$값에 $z_i$를 더하고 $a_{y_i}$값에 $z_i$를 빼야함을 의미합니다.

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

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

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

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

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

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

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

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