A county has n towns numbered 0 .. n-1 and a list of two-way roads. Road roads[i] = [a, b, h] joins towns a and b and passes under a bridge with clearance h: a van of height at most h can use it.
For two towns x and y, the reach height is the height of the tallest van that can drive from x to y along some route (any number of roads). A route lets through vans no taller than its lowest bridge, and the van may pick the best route. If no route joins x and y, their reach height is 0.
Return the sum of the reach heights over all unordered pairs of different towns {x, y}.
Examples
Input: n = 4, roads = [[0, 1, 5], [1, 2, 3], [0, 2, 4], [2, 3, 2]]
Output: 19
Explanation: pair {0,1}: 5. Pair {0,2}: 4 (direct road). Pair {1,2}: 4, going
1 -> 0 -> 2 beats the direct road of height 3. Pairs {0,3}, {1,3}, {2,3}: 2 each,
since every route to town 3 uses the road of height 2. Total 5 + 4 + 4 + 2 + 2 + 2 = 19.
Input: n = 3, roads = []
Output: 0
Input: n = 5, roads = [[0, 1, 7], [3, 4, 2], [3, 4, 9]]
Output: 16
Explanation: {0,1} gives 7, {3,4} gives 9 (the taller of two parallel roads); the other pairs have no route.
Constraints
1 <= n <= 10**5,0 <= len(roads) <= 2 * 10**5a != b; there may be several roads between the same two towns1 <= h <= 10**6- Target: about O(m log m) time for
mroads. Solving each pair (or each starting town) separately is far too slow.
Goals
- Recognise that the best 'weakest link' between two towns is decided by a maximum spanning forest
- Count how many pairs of towns each merge serves, instead of solving every pair separately
- Keep component sizes in union-find and use them to count pairs