Finding a particular path in weighted tree

Question

I have undirected weighted linear tree (path tree) with $n$ nodes ,and a weight function on edges $\omega: \mathbb{N}\to \mathbb{N}$, additionally given $k\in \mathbb{N}$, How we can find a path with lenght $k$ that have minimum number of edges in $O(n)$?

I think as follow: Run Bellman Ford for each node and then select a path with length $k$ and minimum number of edges. Unfortunately runtime $\omega(n)$.

Answer 1

The idea is to find, for each vertex $i$, the first vertex $j_i > i$ such that the distance $d(i, j_i)$ between $i$ and $j_i$ is at least $k$. Then, you can return the pair $(i, j_i)$ such that $d(i,j_i)=k$ and $j_i-i$ is minimized.

This takes $O(n)$ time once you notice that, for $i_1 < i_2$, $j_{i_1} \le j_{i_2}$. In pseudocode, where $w(\ell, \ell+1)$ denotes the weight of edge $(\ell, \ell+1)$:

i = j = 1
best_i = 0
best_j = n
d = 0

while i != n:
  if d<k and j!=n:
    d = d + w(j, j+1)
    j=j+1
  else:
    d = d - w(i, i+1)
    i=i+1

  if d == k and j - i < best_j - best_i:
    best_i=i
    best_j=j

return best_i, best_j