31740번 - Split the SSHS 3 서브태스크스페셜 저지

문제

서울과학고등학교에는 $N$개의 대나무가 $N-1$개의 나무줄기로 연결되어 있는 독특한 형태의 대나무숲이 있다. 각 나무줄기는 대나무 2개를 연결하며 대나무들은 모두 연결되어 있다. 이때 연결되어 있다는 것은 어떤 두 대나무를 골라도 서로 나무줄기를 통해서 이동할 수 있다는 것을 의미한다. 만약 1번과 2번 대나무가 나무줄기로 연결되어 있으면 1번과 2번은 나무줄기를 통해서 서로 이동할 수 있는 것이다. 또한 임의의 두 대나무 사이를 나무줄기를 통해 이동할 수 있는 단순(최단)경로는 유일하다.

대나무숲에서 서울과학고등학교 친구들은 서로를 돕고 의지하며 행복하게 살고 있었다. 하지만 어느 날, 대나무숲 친구들 사이에 갈등이 생겼다. for문에서 중괄호의 위치에 관한 의견을 달리하며 다투게 된 것이다!

결국 다툼에 지친 서울과학고등학교 친구들은 대나무숲을 나누기로 결정했다. 이 때 어느 한쪽이 지나치게 유리하면 다른 쪽의 반발이 생기기 때문에 최대한 공평하게 나눠야 한다.서울과학고등학교 친구들은 대나무숲을 너무나 사랑하기 때문에 단 하나의 나무줄기만 잘라서 대나무숲을 2개로 나누려고 한다.

$i(1\leq i\leq N)$번 대나무는 중요도 $W_i$를 가지고 있으며, 대나무숲의 중요도는 대나무숲에 속한 모든 대나무의 중요도의 합으로 정의한다. 이때, 대나무숲을 공평하게 나눈다는 것은 나눠진 두 대나무숲의 중요도의 차가 최소가 되도록 나눈다는 뜻이다.

대나무숲을 공평하게 나눴을 때 중요도의 차와 이때 끊어야 할 나무줄기가 연결하는 대나무들의 번호를 구해서 귀여운 서울과학고등학교 친구들을 도와주자.

입력

첫 번째 줄에 대나무의 수 $N$이 주어진다.

이후 $N-1$줄에 걸쳐 그중 $i(1 \leq i \leq N-1)$번째 줄에 $i$번째 나무줄기가 연결하는 대나무들의 번호가 공백으로 구분되어 주어진다.

이후 $N$줄에 걸쳐 그중 $i(1 \leq i \leq N)$번째 줄에 $i$번 대나무의 중요도 $W_i$가 주어진다.

출력

첫 번째 줄에 중요도의 차의 최솟값을 출력한다.

두 번째 줄에는 끊어야 할 나무줄기가 잇는 대나무들의 번호 2개를 공백으로 구분하여 출력한다.

가능한 답이 여러 가지 있다면, 그중 어떤 것을 출력해도 좋다.

제한

• 2ドル\leq N\leq 100,000$
• $-10,000 \leq W_i\leq 10,000$
• 문제에서 주어지는 모든 수는 정수이다.

서브태스크

노트

• 차는 다음과 같이 정의된다: $x$와 $y$의 차는 $x-y$와 $y-x$중 작지 않은 수이다.