2011. The Longest Path in the Whole Tree
A tree with n nodes is given as n - 1 weighted edges. Print the largest total
weight of a path between any two nodes. That quantity is the tree's DIAMETER.
``` edges: 1-2 (3) 1-3 (5) 2-4 (2) 2-5 (7)
the best path is 5 - 2 - 1 - 3, total 7 + 3 + 5 = 15 ```
A tree with one node has diameter 0, since the only path has no edges.
## What most people try first
Run a search from every node and keep the largest distance found. That is n
searches of O(n) each, so O(n^2), which at n = 2 * 10^5 is 4 * 10^10
steps.
The instinct to fix it by searching from a leaf, or from the node of highest degree, is worth resisting: neither is right in general, and the version that IS right needs an argument rather than a guess.
## Two searches is enough
a = the node farthest from any starting node
b = the node farthest from a
answer = distance from a to b
## Why the first search lands on an endpoint of a diameter
Let a be the node farthest from the start s, and suppose some diameter runs
between x and y with a on neither end.
Walk from s until its path first meets the diameter, at a node m. Then
dist(s, a) >= dist(s, x) and dist(s, a) >= dist(s, y), because a is
farthest. Since every route from s to x or y passes through m, that
gives dist(m, a) >= dist(m, x) and dist(m, a) >= dist(m, y). So replacing
x by a gives a path from a to y at least as long as the diameter, which
means a IS an endpoint of some diameter.
The tree structure is what makes this work: between any two nodes there is
exactly one route, so "the path meets the diameter at m" is a fact rather than
a choice.
## The trap in the argument
The proof uses non-negative weights. With a negative edge, "farthest" stops behaving and the two-search method quietly returns the wrong number, which is why the constraints keep weights at zero or above.
## Cost
Two linear scans, O(n) total, against O(n^2) for the all-pairs version.
## Overflow
2 * 10^5 edges of 10^9 give a path weight up to about 2 * 10^14, far past
the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 10^9` - the `n - 1` edges always form a tree
Input
The first line contains the integer n.
Each of the next n - 1 lines contains three integers u, v and w: an edge between u and v of weight w.
Output
Print one integer on its own line: the largest total edge weight of any path between two nodes, or 0 when the tree has a single node.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.