2376번 - 단말 정점들의 거리

문제

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번 단말 정점 사이의 거리가 주어진다. 다음 줄에는 거리를 알고자 하는 서로 다른 두 단말 정점의 번호가 주어진다.

출력

첫째 줄에 거리를 출력한다.

제한

힌트