The problem
A railway company has n stations joined by n − 1 roads, so that there is exactly one way between any two stations: the roads form a tree. Each road is given as (u, v, length), in either direction. For every station, return the total of its distances to all the other stations.
total_distance(4, [(0, 1, 1), (1, 2, 1), (2, 3, 1)])
# [6, 4, 4, 6]
total_distance(3, [(0, 1, 2), (1, 2, 10)]) # [14, 12, 22]
Limits
- Up to 100,000 stations; lengths from 0 to 1,000.
- The tree can be a single line of 100,000 stations, so a recursive search runs out of depth.
- A search from every station takes about 10¹⁰ steps. Aim for O(n).
Builds on ADDP-1 DP on trees.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
11 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | One station | Not run | |
| 2 | Two stations | Not run | |
| 3 | A line of four | Not run | |
| 4 | Lengths matter | Not run | |
| 5 | A star | Not run | |
| 6 | Roads listed the other way round | Not run | |
| 7 | A road of length 0 | Not run | |
| 8 | The figure's tree, with lengths | Not run | |
| 9 | A long line | Not run | |
| 10 | 100,000 stations, random | Not run | |
| 11 | A broom | Not run |