Розбір

For a tree, it's a pretty well-known problem, but let's remind the solution.

Let's process the nodes in order from the smallest weight to the largest, keeping the current right end $r$. For each node with weight $i$ from $1$ to $r$, we will also keep t