# Finding a particular path in weighted tree

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)$$.

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

• $j_i-i$ must maximized? i think must minimized.
– user133520
Commented Mar 24, 2021 at 21:39
• @myarge. My bad. I fixed it. It doesn't make much of a difference anyway. Commented Mar 24, 2021 at 21:41
• Hello, could you explain you idea in simple manner? Thank you. Commented Apr 27, 2022 at 22:35
• Scan the vertices of the path from left to right. For each vertex $i$, find the right endpoint as the leftmost vertex $j$ that is "to the right" of $i$ has is at a distance of at least $k$. The solution can be found by examining only these pairs $(i,j)$. To get a running time of $O(n)$ you can notice that the position of the vertices $j$ must either stay the same or move right, when $i$ changes. Commented Apr 28, 2022 at 8:02
• Thank you. If the our tree has at most degree 3 for each vertex, can we solve the problem in $O(n^2\log n)$? Commented Apr 28, 2022 at 8:26