Split the SSHS 3
시간 제한1초메모리 제한1024 MB
가중치가 있는 트리에서 간선 하나를 잘라 두 부분으로 나눌 때, 두 부분의 가중치 합 차이의 절댓값을 최소로 하는 간선을 찾는다.
문제
서울과학고등학교에는 개의 대나무가 개의 나무줄기로 연결되어 있는 독특한 형태의 대나무숲이 있다. 각 나무줄기는 대나무 2개를 연결하며 대나무들은 모두 연결되어 있다. 이때 연결되어 있다는 것은 어떤 두 대나무를 골라도 서로 나무줄기를 통해서 이동할 수 있다는 것을 의미한다. 만약 1번과 2번 대나무가 나무줄기로 연결되어 있으면 1번과 2번은 나무줄기를 통해서 서로 이동할 수 있는 것이다. 또한 임의의 두 대나무 사이를 나무줄기를 통해 이동할 수 있는 단순(최단)경로는 유일하다.
대나무숲에서 서울과학고등학교 친구들은 서로를 돕고 의지하며 행복하게 살고 있었다. 하지만 어느 날, 대나무숲 친구들 사이에 갈등이 생겼다. for문에서 중괄호의 위치에 관한 의견을 달리하며 다투게 된 것이다!
결국 다툼에 지친 서울과학고등학교 친구들은 대나무숲을 나누기로 결정했다. 이 때 어느 한쪽이 지나치게 유리하면 다른 쪽의 반발이 생기기 때문에 최대한 공평하게 나눠야 한다.서울과학고등학교 친구들은 대나무숲을 너무나 사랑하기 때문에 단 하나의 나무줄기만 잘라서 대나무숲을 2개로 나누려고 한다.
번 대나무는 중요도 를 가지고 있으며, 대나무숲의 중요도는 대나무숲에 속한 모든 대나무의 중요도의 합으로 정의한다. 이때, 대나무숲을 공평하게 나눈다는 것은 나눠진 두 대나무숲의 중요도의 차가 최소가 되도록 나눈다는 뜻이다.
대나무숲을 공평하게 나눴을 때 중요도의 차와 이때 끊어야 할 나무줄기가 연결하는 대나무들의 번호를 구해서 귀여운 서울과학고등학교 친구들을 도와주자.
입력
첫 번째 줄에 대나무의 수 이 주어진다.
이후 줄에 걸쳐 그중 번째 줄에 번째 나무줄기가 연결하는 대나무들의 번호가 공백으로 구분되어 주어진다.
이후 줄에 걸쳐 그중 번째 줄에 번 대나무의 중요도 가 주어진다.
출력
첫 번째 줄에 중요도의 차의 최솟값을 출력한다.
두 번째 줄에는 끊어야 할 나무줄기가 잇는 대나무들의 번호 2개를 공백으로 구분하여 출력한다.
가능한 답이 여러 가지 있다면, 그중 어떤 것을 출력해도 좋다.
제한
- 문제에서 주어지는 모든 수는 정수이다.
힌트
- 차는 다음과 같이 정의된다: 와 의 차는 와 중 작지 않은 수이다.