대피소 사이 거리

200점케이스 15출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

한 산에는 대피소가 N개 있고, 각 대피소에는 1번부터 N번까지 번호가 붙어 있다. 대피소 사이에는 등산로가 N-1개 놓여 있는데, 등산로마다 두 대피소를 직접 이어 주고 그 길의 길이가 정해져 있다. 이 N-1개의 등산로를 따라가면 어느 대피소에서 어느 대피소로도 갈 수 있고, 두 대피소를 잇는 길은 언제나 한 가지뿐이다.

관리 사무소에는 등산객의 문의가 M번 들어온다. 각 문의는 대피소 두 곳의 번호를 말하고, 앞의 대피소에서 뒤의 대피소까지 등산로를 따라 갔을 때의 거리를 묻는다. 거리는 지나간 등산로의 길이를 모두 더한 값이다. 두 대피소를 잇는 길이 한 가지뿐이므로 거리도 하나로 정해진다. 두 대피소의 번호가 같은 문의도 들어올 수 있는데, 이 경우에는 어디로도 갈 필요가 없으므로 거리가 0이다.

등산로의 정보와 M번의 문의가 주어졌을 때, 각 문의에 대한 거리를 차례대로 계산하는 프로그램을 작성하여라.

예를 들어 N=4개의 대피소가 있고, 등산로 3개가 다음의 표와 같이 놓여 있다고 해보자.

등산로 번호	1	2	3
한쪽 대피소	2	4	1
다른 쪽 대피소	1	3	4
길의 길이	2	2	3

이후에 M=2번의 문의가 차례대로 들어왔다고 가정하자. 첫 번째 문의는 1번에서 3번까지의 거리를 묻는다. 1번에서 3번으로 가려면 1번에서 4번으로 간 뒤 4번에서 3번으로 가야 하므로 거리는 3 + 2 = 5다. 두 번째 문의는 2번에서 4번까지의 거리를 묻는다. 2번에서 4번으로 가려면 2번에서 1번으로 간 뒤 1번에서 4번으로 가야 하므로 거리는 2 + 3 = 5다.

문의 번호	1	2
출발 대피소	1	2
도착 대피소	3	4
거리	5	5

따라서 현재 예시의 정답은 차례대로 5와 5다. 두 문의의 답이 같은 값이 되었지만 지나간 등산로는 서로 다르다.

한편 출발 대피소와 도착 대피소가 같은 문의도 들어온다. 예를 들어 1번에서 1번까지의 거리를 묻는 문의가 들어오면 어디로도 갈 필요가 없으므로 답은 0이다.

입출력 예시

예시 1

입력

출력

5
5

예시 2

입력

출력

420
420
0

예시 3

입력

출력

입력 조건

가장 먼저 첫째 줄에 대피소의 개수 N과 문의의 개수 M이 공백을 두고 주어진다. N은 2 이상 1,000 이하의 자연수이고, M은 1 이상 1,000 이하의 자연수다.
이어서 N-1개의 줄에 걸쳐 각 등산로의 정보가 주어진다. 각 줄에는 등산로가 잇는 두 대피소의 번호와 그 길의 길이가 공백을 두고 주어진다. 두 번호는 1 이상 N 이하의 자연수이고, 길의 길이는 1 이상 1,000 이하의 자연수다.
이어서 M개의 줄에 걸쳐 각 문의의 정보가 주어진다. 각 줄에는 출발 대피소의 번호와 도착 대피소의 번호가 공백을 두고 주어지며, 두 번호는 모두 1 이상 N 이하의 자연수다.

출력 조건

M번의 문의에 대하여, 두 대피소 사이를 등산로를 따라 갔을 때의 거리를 한 줄에 하나씩 차례대로 출력한다. 문의가 들어온 순서를 그대로 지킨다. 두 대피소의 번호가 같은 문의에는 0을 출력한다.

요구사항

등산로는 N-1개이며, 이 길만으로 어느 대피소에서 어느 대피소로도 갈 수 있습니다
두 대피소를 잇는 길은 한 가지뿐입니다
거리는 지나간 등산로의 길이를 모두 더한 값입니다
문의마다 답을 한 줄에 하나씩 출력합니다
두 대피소의 번호가 같은 문의의 답은 0입니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 15개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

입력

기대 출력

420
420
0

5
5

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 43ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.