Finding a particular path in weighted tree
The idea is to find, for each vertex $i$, the first vertex $j_i &gt; i$ such that the distance $d(i, j_i)$ between $i$ and $i_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 &lt; 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&lt;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 &lt; best_j - best_i:
    best_i=i
    best_j=j

return best_i, best_j