The longest span
Towns are joined by communication lines, and the network is a tree: there is exactly one path along the lines between any two towns. A line between neighbouring towns is one span, and the longer it is, the dearer it is to maintain and the likelier the signal fades on it. For a pair of towns you need to know the longest span on the path between them.
The third test is real towns: all 126 towns and settlements with a population of 10,000 or more within 500 km of Almaty (GeoNames), joined by a minimum spanning tree; the span lengths are straight-line distances over the Earth’s surface in kilometres. Every pair is asked about.
Input
The first line holds n (1 ≤ n ≤ 100,000). Then come n − 1 lines a b w: a span of length w between towns a and b (1 ≤ w ≤ 109); together they form a tree. Then the number of questions q (1 ≤ q ≤ 50,000) and q lines u v.
Output
For each question, the length of the longest span on the path from u to v; if u = v, the path is empty, and the answer is 0.
Examples
Example 1
5 1 2 5 1 3 9 2 4 3 3 5 2 3 4 5 4 2 3 3
9 3 0
Example 2
6 1 2 40 2 3 75 3 4 20 2 5 60 5 6 90 4 4 6 1 4 6 5 3 1
90 75 90 75
Limits
- Time · Python
- 5000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The path from u to v in a tree is a climb from u to their common ancestor and a climb from v to the same. The maximum on the path is the larger of the two maxima on the climbs.
2Hint 2
A binary lifting table stores where a jump of 2k steps leads. What else can be stored about this jump so as not to go over its steps?
3The idea
Beside the ancestor up[k][v] 2k steps up, store most[k][v], the longest span on these 2k steps. A jump of 2k is two jumps of 2k−1, so most[k][v] = max(most[k−1][v], most[k−1][up[k−1][v]]). Then the usual search for the common ancestor by binary lifting, only each jump updates the answer with the maximum of its spans.
4Walkthrough
Hang the tree from town 1 with a breadth-first walk: in walk order a parent always comes before its child, and the tables are built by simple passes. most[0][v] is the length of the span from v to its parent, 0 at the root, and the root is its own parent. A question: raise the deeper vertex by the difference in depth, collecting the maximum; if the vertices coincide, done. Otherwise jump with both while the ancestors differ, collecting the maxima of both. At the end both stand right under the common ancestor, and the last two spans, into the common ancestor itself, must be added separately: most[0][a] and most[0][b].
In the first example the path 4 → 5 is 4, 2, 1, 3, 5 with spans 3, 5, 9, 2. The jumps would bring the vertices to 2 and 3 with a maximum of 3, while the longest span, 9 km, is exactly one of the last two.
Why the third test takes a minimum spanning tree: the path in it between two towns is the very path in the whole “everyone with everyone” network whose longest span is the smallest possible. This follows from the cut property on which the minimum spanning tree rests. The longest span in the whole network around Almaty is 203 km.
4+Solution
5Complexity
Preparation O(n log n) time and memory, a question O(log n).
6Common mistakes
- Forgotten last spans. After the jumps the vertices stand under the common ancestor, but the two spans into it are not yet counted. The first example is built exactly on this.
- Climbing a step at a time. On deep trees each question costs the height of the tree; in the fifth test the tree is about 25 thousand deep.
- A recursive walk. Hanging the tree by recursion in Python is not possible: on a tree tens of thousands deep the stack runs out.
Algorithms behind it
O(log n) per query
2 problems
GRA
Algorithm
Minimum spanning tree
The cheapest network connecting all vertices: Borůvka, Kruskal and Prim, three ways to apply one lemma.
O(E log V)
2 problems