Count the Number of Houses at a Certain Distance II

Count, for each k, the number of ordered pairs of nodes in a path graph of n houses with one extra shortcut edge (x,y) whose shortest-path distance equals k. The challenge is to efficiently tally pairs for every k by comparing the direct distance |i−j| with distances that go through the shortcut, avoiding O(n^2) pairwise checks.