단말 정점 사이의 거리
시간 제한2초메모리 제한128 MB
인오더로 번호가 매겨진 이진 트리에서 인접한 리프 간 거리들이 주어질 때, 임의의 두 리프 사이 거리를 구해야 합니다.
문제
n개의 단말 정점을 가진 루트 있는 이진 트리가 있다. 단말 정점은 자식이 없는 정점이다. 이 트리를 중위 순회했을 때 만나는 순서대로 단말 정점에 1, 2, ..., n의 번호가 붙어 있다. 자식이 있는 모든 정점은 정확히 두 개의 자식을 가진다.
1 <= k < n인 모든 정수 k에 대해, k번 단말 정점과 k + 1번 단말 정점 사이의 거리가 주어진다. 이 정보만으로 임의의 두 단말 정점 사이의 거리를 알 수 있다. 서로 다른 두 단말 정점의 번호가 주어졌을 때, 두 정점 사이의 거리를 구하시오.
입력
첫째 줄에 단말 정점의 개수 n (2 <= n <= 1,000)이 주어진다.
다음 n - 1개의 줄에는 차례대로 1번과 2번 단말 정점 사이의 거리, 2번과 3번 사이의 거리, ..., n - 1번과 n번 사이의 거리가 주어진다.
다음 줄에는 거리를 알고자 하는 서로 다른 두 단말 정점의 번호가 주어진다.
출력
첫째 줄에 거리를 출력한다.