Courier Lulu

Process the bridges in decreasing order of box size.

Let $dp[x]$ be the maximum number of boxes that can be collected when Lulu ends at island $x$ using only bridges whose box sizes are larger than the current bridge's size.

Suppose the current bridge connects $u$ and $v$ and has box size $c$. If this bridge is used as the last bridge, every previously collected box must have size greater than $c$. Therefore, all valid previous states are already represented in $dp$.

There are two possible transitions.

• Lulu is at island $u$ and crosses this bridge to island $v$.
• Lulu is at island $v$ and crosses this bridge to island $u$.

Thus we update:

$$\begin{aligned} dp[v] &\leftarrow \max(dp[v], dp[u] + 1),\\ dp[u] &\leftarrow \max(dp[u], dp[v] + 1). \end{aligned}$$

However, the two updates must use the old values of $dp[u]$ and $dp[v]$, so that the same bridge is not used twice during one transition.

Since all box sizes are distinct, we do not need to group bridges with equal sizes.

Each bridge is processed once, and sorting takes $O(M \log M)$ time. The total time complexity is $O(M \log M)$, and the memory complexity is $O(N+M)$.