시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 394 | 158 | 125 | 40.453% |
n개의 단말 정점을 갖는 루트가 있는 이진 트리(Rooted binary tree)가 있다. 단말 정점은 자식 정점이 없는 정점을 말한다. 주어진 트리를 인오더로 탐색하였을 때 단말 정점들이 나오는 순서대로 단말 정점들에 1, 2, …, n의 번호가 붙어 있다. 주어진 트리에서 만약 어떤 정점에 자식 정점이 있다면, 그 정점은 반드시 두 개의 자식 정점을 갖는다고 하자.
n보다 작은 자연수 k에 대해서, 우리는 k번 단말 정점과 k+1번 단말 정점의 거리를 알고 있다. 이러한 정보를 알고 있으면, 이를 이용하여 임의의 두 단말 정점 사이의 거리를 알 수 있다. 이를 구하는 프로그램을 작성하시오.
첫째 줄에 단말 정점의 개수 n(2 ≤ n ≤ 1,000)이 주어진다. 다음 n-1개의 줄에는 차례로 1, 2번 단말 정점 사이의 거리, 2, 3번 단말 정점 사이의 거리, …, n-1, n번 단말 정점 사이의 거리가 주어진다. 다음 줄에는 거리를 알고자 하는 서로 다른 두 단말 정점의 번호가 주어진다.
첫째 줄에 거리를 출력한다.
4 4 2 3 1 3
4