Distances Between Leaf Vertices
Time limit2sMemory limit128 MB
Given consecutive-leaf distances of an inorder-numbered binary tree, compute the distance between two arbitrary leaves using a sparse-table style max-range query derived from LCA depth relations.
- Level
Medium6 of 10
- Topics
- Tree, Segment tree, Dynamic programming
- Solved
- No attempts yet
Problem
A rooted binary tree has n leaf vertices. A leaf vertex is a vertex with no children. When the tree is traversed inorder, the leaf vertices are numbered 1, 2, ..., n in the order they appear. Every vertex that has children has exactly two children.
For each integer k with 1 <= k < n, the distance between leaf vertex k and leaf vertex k + 1 is known. This information is enough to determine the distance between any two leaf vertices. Given two distinct leaf vertex numbers, compute their distance.
Input
The first line contains the number of leaf vertices n (2 <= n <= 1,000).
The next n - 1 lines contain, in order, the distance between leaf vertices 1 and 2, the distance between 2 and 3, ..., and the distance between n - 1 and n.
The next line contains two distinct leaf vertex numbers whose distance must be found.
Output
Print the distance on the first line.